The Regularity Method for Sparse Graphs and Hypergraphs

• Applicant: Professor Dr. Mathias Schacht
• Subject Area: Mathematics
• Term: from 2005 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5443326

• Final Report Year: 2008

Final Report Abstract

The research in the funding period has mainly been focused on extensions and applications of the regularity method, which has had a series of successes in discrete mathematics. The regularity method for graphs is the key ingredient for the proof of the so-called graph removal lemma. This lemma asserts that every graph that does not contain "many" copies of a given fixed graph F can be made F-free by deleting "few" edges. Surprisingly, all known proofs for this "innocent" looking lemma are based on regularity method for graphs and variants of this. Recently the regularity method was generalized for fc-uniform hypergraphs and a corresponding removal lemma was obtained. During the funded period the PI focused on the further development and applications of the regularity method for hypergraphs. In particular, a generalization of the removal lemma for infinite families and induced containment was obtained in joint work with Rödl [RS07a, RS], Moreover, the stronger versions of the hypergraph regularity lemma were developed [RS07c, RS07b]. With those stronger versions several extremal hypergraph problems became approachable and in joint work with several collaborators, the PI obtained Ramsey type results [NORS], Turan type results [NRS06b], and hypergraph packing results [RSST07]. Moreover, the regularity method developed in [RSOTc, RS07b] has already been used by other researchers [CFKO]. The PI also worked on several problems in extremal graph theory. In joint work with Böttcher and Taraz [BSTb, BSTa] a conjecture of Bollobas and Komlos concerning spanning subgraphs of dense graphs was resolved. This result generalizes several earlier results of various researchers and its proof relies on the regularity method for graphs. We also obtained an algorithmic version of the regularity lemma for subgraphs of sparse quasirandorn graphs [ACOH+, ACOH+07] and a Turan type result for sparse quasirandom graphs [KRS+07]. In total the work on this project resulted in 18 contributions submitted to international journals of discrete and general mathematics and 5 extended abstracts presented at international conferences in the area. One publication [RNS+05] appeared in the Proceedings of the National Academy of Sciences, USA.

Publications

• Y. Kohayakawa, V. Rödl, M. Schacht, P. Sissokho, and J. Skokan, Turan's theorem for pseudo-random graphs, Journal of Combinatorial Theory (A) 114 (2007), no. 4, 631 657.
  
  
• B. Bollobas, Y. Kohayakawa, V. Rödl, M. Schacht, and A. Taraz, Essentially infinite colourings of hypergraphs, Proceedings of the London Mathematical Society 95 (2007), no. 3, 709 734.
  
  
• B. Nagle, V. Rödl, and M. Schacht, Extremal hypergraph problems and the regularity method, Topics in Discrete Mathematics (M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, and P. Valtr, eds.), Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 247 278.
  
  
• B. Nagle, V. Rödl, and M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures and Algorithms 28 (2006), no. 2, 113-179.
  
  
• C. Avart, V. Rödl, and M. Schacht, Every monotone 3-graph property is testable, 7th International Colloquium on Graph Theory (Amsterdam), Electron. Notes Discrete Math., vol. 22, 2005, pp. 539-542.
  
  
• C. Avart, V. Rödl, and M. Schacht, Every monotone 3-graph property is testable, SIAM Journal on Discrete Mathematics 21 (2007), no. l, 73-92.
  
  
• J. Bang-Jensen, B. Reed, M. Schacht, R. Sämal, B. Toft, and U. Wagner, On six problems posed by Jarik Nesetfil, Topics in Discrete Mathematics (M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, and P. Valtr, eds.), Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 613-627.
  
  
• J. Böttcher, M. Schacht, and A. Taraz, Embedding spanning subgraphs of small bandwidth, Proceedings of EuroComb 07, Electron. Notes Discrete Math., vol. 29, 2007, pp. 485 489.
  
  
• J. Böttcher, M. Schacht, and A. Taraz, On the bandwidth conjecture for 3-colourable graphs, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 07) (H. Gabow, ed.), ACM Press, 2007, pp. 618-626.
  
  
• N. Alon, A. Coja-Oghlan, H. Han, M. Kang, V. Rödl, and M. Schacht, Quasirandomness and algorithmic regularity for graphs with general degree distributions, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, Lecture Notes in Computer Science, vol. 4596, Springer, 2007, pp. 789 800.
  
  
• V. Rödl and M. Schacht, Property testing in hypergraphs and the removal lemma, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, June 11-13, 2007 (D. S. Johnson and U. Feige, eds.), ACM Press, 2007, pp. 488 495.
  
  
• V. Rödl and M. Schacht, Regular partitions of hypergraphs: Counting lemmas, Combinatorics, Probability and Computing 16 (2007), no. 6, 887-901.
  
  
• V. Rödl and M. Schacht, Regular partitions of hypergraphs: Regularity lemmas, Combinatorics, Probability and Computing 16 (2007), no, 6, 833 885,
  
  
• V. Rödl, A. Ruciriski, and M. Schacht, Ramsey properties of random k-partite kunifam hypergraphs, SIAM Journal on Discrete Mathematics 21 (2007), no. 2, 442 460.
  
  
• V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa, The hypergraph regularity method and its applications, Proceedings of the National Academy of Sciences USA 102 (2005), no. 23, 8109-8113.
  
  
• V. Rödl, M. Schacht, E. Tengan, and N. Tokushige, Density theorems and extremal hypergraph problems, Israel Journal of Mathematics 152 (2006), 371-380.
  
  
• V. Rödl, M. Schacht, M. Siggers, and N. Tokushige, Integer and fractional packings of hypergraphs, Journal of Combinatorial Theory (B) 97 (2007), no. 2, 245-268.