Publications

Articles

Preprints

• V. Rödl, M. Schacht, Extremal results in random graphs, submitted
• S. Messuti, M. Schacht, On the structure of graphs with given odd girth and large minimum degree, submitted
• E. Aigner-Horev, H. Hàn, M. Schacht, Extremal results for odd cycles in sparse pseudorandom graphs, submitted
• E. Buß, H. Hàn, M. Schacht, Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs, submitted
• M. Schacht, Extremal results for random discrete structures, submitted

• Y. Kohayakawa, M. Schacht, R. Spöhel, Upper bounds on probability thresholds for asymmetric Ramsey properties, Random Structures and Algorithms, to appear

2012

• D. Conlon, H. Hàn, Y. Person, M. Schacht, Weak quasi-randomness for uniform hypergraphs, Random Structures and Algorithms, 40(1), 1-38
• D. Dellamonica Jr., P. Haxell, T. Łuczak, D. Mubayi, B. Nagle, Y. Person, V. Rödl, M. Schacht, Tree-minimal graphs are almost regular, Journal of Combinatorics, 3(1), 49-62
• D. Dellamonica Jr., P. Haxell, T. Łuczak, D. Mubayi, B. Nagle, Y. Person, V. Rödl, M. Schacht, J. Verstraëte, On even-degree subgraphs of linear hypergraphs, Combinatorics, Probability and Computing, 21(1-2), 113-127
• V. Rödl, M. Schacht, Complete partite subgraphs in dense hypergraphs, Random Structures and Algorithms, 41(4), 557-573

2011

• M. Kang, O. Pikhurko, A. Ravsky, M. Schacht, O. Verbitsky, Untangling planar graphs from a specified vertex position – Hard cases, Discrete Applied Mathematics 159(8), 789-799
• Y. Kohayakawa, V. Rödl, M. Schacht, E. Szemerédi, Sparse partition universal graphs for graphs of bounded degree, Advances in Mathematics 226(6), 5041-5065
• Y. Person, M. Schacht, An expected polynomial time algorithm for coloring 2-colorable 3-graphs, Discrete Mathematics & Theoretical Computer Science, 13(2), 1-18;
  Extended abstract appeared in Electron. Notes Discrete Math. 34, 465-469

2010

• N. Alon, A. Coja-Oghlan, H. Hàn, M. Kang, V. Rödl, M. Schacht, Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions, SIAM Journal on Computing 39(6), 2336-2362;
  Extended abstract appeared in Proceedings of ICALP 2007, 789-800
• E. Friedgut, V. Rödl, M. Schacht, Ramsey properties of random discrete structures, Random Structures and Algorithms 37(4), 407-436
• H. Hàn, M. Schacht, Dirac-type results for loose Hamilton cycles in uniform hypergraphs, Journal of Combinatorial Theory (B) 100(3), 332-346
• J. Hladký, M. Schacht, Note on bipartite graph tilings, SIAM Journal on Discrete Mathematics 24(2), 357-362
• Y. Kohayakawa, B. Nagle, V. Rödl, M. Schacht, Weak regularity and linear hypergraphs, Journal of Combinatorial Theory (B) 100(2), 151-160
• Y. Kohayakawa, V. Rödl, M. Schacht, J. Skokan, On the triangle removal lemma for subgraphs of sparse pseudorandom graphs, An Irregular Mind (Szemerédi is 70), vol. 21 series Bolyai Soc. Math. Stud., 359-404
• H. Lefmann, Y. Person, M. Schacht, A structural result for hypergraphs with many restricted edge colorings, Journal of Combinatorics 1(3-4), 441-475
• V. Rödl, M. Schacht, Regularity lemmas for graphs, Fete of Combinatorics and Computer Science, vol. 20 series Bolyai Soc. Math. Stud., 287-325

2009

• J. Böttcher, M. Schacht, A. Taraz, Proof of the bandwidth conjecture of Bollobás and Komlós, Math. Ann. 343(1), 175-205;
  Extended abstract appeared in Electron. Notes Discrete Math. 29, 485-489
• H. Hàn Y. Person, M. Schacht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM Journal on Discrete Mathematics 23(2), 732-748
• H. Lefmann, Y. Person, V. Rödl, M. Schacht, On colorings of hypergraphs without monochromatic Fano planes, Combinatorics, Probability and Computing 18(5), 803-818
• V. Rödl, M. Schacht, Generalizations of the removal lemma, Combinatorica 29(4), 467-501;
  Extended abstract appeared in Proceedings of STOC 2007, 488-495

2008

• J. Böttcher, M. Schacht, A. Taraz, Spanning 3-colourable subgraphs of small bandwidth in dense graphs, Journal of Combinatorial Theory (B) 98(4), 752-777;
  Extended abstract appeared in Proceedings of SODA 2007, 618-626
• B. Nagle, S. Olsen, V. Rödl, M. Schacht, On the Ramsey number of sparse 3-graphs, Graphs and Combinatorics 24(3), 205-228
• B. Nagle, V. Rödl, M. Schacht, Note on the 3-graph counting lemma, Discrete Mathematics 308(19), 4501-4517
• V. Rödl, A. Ruciński, M. Schacht, E. Szemerédi, A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Commentationes Mathematicae Universitatis Carolinae 49(4), 633-636

2007

• Chr. Avart, V. Rödl, M. Schacht, Every monotone 3-graph property is testable, SIAM Journal on Discrete Mathematics 21(1), 73-92;
  Extended abstract appeared in: Electron. Notes Discrete Math. 22, 539-542
• B. Bollobás, Y. Kohayakawa, V. Rödl, M. Schacht, A. Taraz, Essentially infinite colourings of hypergraphs, Proceedings of the London Mathematical Society 95(3), 709-734;
  Extended abstract appeared in: Electron. Notes Discrete Math. 19, 179-185
• Y. Kohayakawa, V. Rödl, M. Schacht, P. Sissokho, J. Skokan, Turán's theorem for pseudo-random graphs, Journal of Combinatorial Theory (A) 114(4), 631-657
• V. Rödl, M. Schacht, Regular partitions of hypergraphs: Regularity Lemmas, Combinatorics, Probability and Computing 16(6), 833-885
• V. Rödl, M. Schacht, Regular partitions of hypergraphs: Counting Lemmas, Combinatorics, Probability and Computing 16(6), 887-901
• V. Rödl, A. Ruciński, M. Schacht, Ramsey properties of random k-partite k-uniform hypergraphs, SIAM Journal on Discrete Mathematics 21(2), 442-460
• V. Rödl, M. Schacht, M. Siggers, N. Tokushige, Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory (B) 97(2), 245-268

2006

• J. Bang-Jensen, B. Reed, R. Šámal, M. Schacht, B. Toft, U. Wagner, On six problems posed by Jarik Nešetřil, Topics in Discrete Mathematics, vol. 26 series Algorithms Combin., 613-627
• B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures and Algorithms 28(2), 113-179
• B. Nagle, V. Rödl, M. Schacht, Extremal hypergraph problems and the regularity method, Topics in Discrete Mathematics, vol. 26 series Algorithms Combin., 247-278
• V. Rödl, M. Schacht, E. Tengan, N. Tokushige, Density theorems and extremal hypergraph problems, Israel Journal of Mathematics 152, 371-380

2005

• V. Rödl, B. Nagle, J. Skokan, M. Schacht, Y. Kohayakawa, The hypergraph regularity method and its applications, Proceedings of the National Academy of Sciences USA 102(23), 8109-8113

2004

• Y. Kohayakawa, V. Rödl, M. Schacht, The Turán theorem for random graphs, Combinatorics, Probability and Computing 13(1), 61-91

Extended abstracts

2011

• E. Buß, H. Hàn, M. Schacht, Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs, Proceedings of EuroComb 2011, vol. 38 series Electron. Notes Discrete Math., 207-212
• H. Hàn, Y. Person, M. Schacht, Note on forcing pairs, Proceedings of EuroComb 2011, vol. 38 series Electron. Notes Discrete Math., 437-442

2009

• H. Hàn, Y. Person, M. Schacht, Note on strong refutation algorithms for random k-SAT formulas, Proceedings of LAGOS 2009, vol. 35 series Electron. Notes Discrete Math., 157-162
• B. Nagle, A. Poerschke, V. Rödl, M. Schacht, Hypergraph regularity and quasi-randomness, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), 227-235
• Y. Person, M. Schacht, An expected polynomial time algorithm for coloring 2-colorable 3-graphs, Proceedings of EuroComb 09, vol. 34 series Electron. Notes Discrete Math., 465-469, full article
• Y. Person, M. Schacht, Almost all hypergraphs without Fano planes are bipartite, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 09), 217-226

2007

• N. Alon, A. Coja-Oghlan, H. Hàn, M. Kang, V. Rödl, M. Schacht, Quasi-randomness and algorithmic regularity for graphs with general degree distributions, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wrocław, Poland, July 9-13, vol. 4596 series Lecture Notes in Computer Science, 789-800, full article
• J. Böttcher, M. Schacht, A. Taraz, Embedding spanning subgraphs of small bandwidth, Proceedings of EuroComb 07, vol. 29 series Electron. Notes Discrete Math., 485-489, full article
• J. Böttcher, M. Schacht, A. Taraz, On the bandwidth conjecture for 3-colourable graphs, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 07), 618-626, full article
• V. Rödl, M. Schacht, Property testing in hypergraphs and the removal lemma, Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 07), 488-495, full article

2005

• Chr. Avart, V. Rödl, M. Schacht, Every Monotone 3-Graph Property is Testable, Seventh International Colloquium on Graph Theory, vol. 22 series Electron. Notes Discrete Math., 539-542, full article
• M. Schacht, A. Taraz, Globally bounded local edge colourings of hypergraphs, Proceedings of GRACO 2005, vol. 19 series Electron. Notes Discrete Math., 179-185, full article

2003

• Y. Kohayakawa, V. Rödl, M. Schacht, Discrepancy and Eigenvalues of Cayley Graphs, Eurocomb 2003, vol 145 series ITI of Charles University, Prague, 242-246

Theses

• M. Schacht, Regular partitions of hypergraphs and property testing, Habilitationsschrift, Humboldt Universität zu Berlin, Institut für Informatik, 2009/10
• M. Schacht, On the regularity method for hypergraphs, Ph.D. thesis, Emory University, Department of Mathematics and Computer Science, May 2004
• M. Schacht, A Turán theorem for random graphs, Master's thesis, Emory University, Department of Mathematics and Computer Science, December 2002

Lecture notes

• M. Schacht, Ramsey Theory, Universität Hamburg, Fachbereich Mathematik, 2011

Other notes

• Foliensatz Grundlagen der Mathematik für die Vorlesung Lineare Algebra und Analytische Mathematik I, Universität Hamburg, Fachbereich Mathematik, 2011
• Zusatzmaterial für die Vorlesung Graphentheorie II, Universität Hamburg, Fachbereich Mathematik, 2011
  • Schrijvers Beweis von Maders Satz über kreuzungsfreie H-Wege
  • Listenfärbungen und Durchschnittsgrad