Embedding spanning subgraphs into dense graphs via the regularity method

• Applicant: Professor Dr. Anusch Taraz
• Subject Area: Mathematics
• Term: from 2007 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 43496149

• Final Report Year: 2014

Final Report Abstract

The main theme of this research project was to determine essentially best-possible sufficient conditions for the embedding of large substructures into dense graphs. Its first aim was to prove the bandwidth conjecture proposed by Bollobás and Komlós, which states that any graph of sufficiently high minimum degree must contain a copy of any degreebounded spanning subgraph of sublinear bandwidth. Subsequently, the project then focused on a variety of closely related embedding problems and investigated • the nature of the bandwidth condition, • subgraphs of unbounded maximum degree and arbitrary order, • sparse host graphs and resilience type questions, • host graphs with median degree conditions, • packings of exhaustive families of trees, • related Ramsey type questions, and • coprime labellings. The key machinery has been the regularity method, but the challenges listed above required the development of new techniques such as a blow-up lemma for arrangeable graphs, a different approach for connecting partial copies within sparse graphs, and quasi-random embeddings via limping homomorphisms. In this way the project succeeded in making progress on a set of important open problems and conjectures in extremal combinatorics while simultaneously advancing the methodology.

Publications

• Proof of the bandwidth conjecture of Bollobás and Komlós, Mathematische Annalen, (2009) 343(1), 175-205
  J. Böttcher, M. Schacht and A. Taraz
  
• Bandwidth, expansion, treewidth, separators, and universality for bounded degree graphs, European Journal of Combinatorics, (2010) 31(5), 1217-1227
  J. Böttcher, K.P. Pruessmann, A. Taraz and A. Würfl
  
• Embedding into bipartite graphs, SIAM Journal on Discrete Mathematics, (2010) 24(4), 1215-1233
  J. Böttcher, P. Heinig and A. Taraz
  
• Prime labellings of trees, Journal of Combinatorics, (2011) 2, 481-500
  P.E. Haxell, O. Pikhurko and A. Taraz
  
• Perfect graphs of fixed density: counting and homogenous sets, Combinatorics, Probability and Computing, (2012) 21(5), 661-682
  J. Böttcher, A. Taraz and A. Würfl
  
• Almost spanning subgraphs of random graphs after adversarial edge removal, Combinatorics, Probability and Computing, (2013) 22(5), 639-683
  J. Böttcher, Y. Kohayakawa and A. Taraz
  (See online at https://doi.org/10.1017/S0963548313000199)
• An Extension of the Blow-Up Lemma to arrangeable graphs. SIAM Journal on Discrete Mathematics, 29(2), 962–1001
  J. Böttcher, Y. Kohayakawa, A. Taraz and A. Würfl
  (See online at https://doi.org/10.1137/13093827X)
• An approximate version of the tree packing conjecture. Israel Journal of Mathematics, February 2016, Volume 211, Issue 1, pp 391–446
  J. Böttcher, J. Hladký, D. Piguet and A. Taraz
  (See online at https://doi.org/10.1007/s11856-015-1277-2)
• Spanning embeddings of arrangeable graphs with sublinear bandwidth. Randon structures & algorithms, Vol 48 Issue 2, March 2016, Pages 270-289. First published: 07 July 2015
  J. Böttcher, A. Taraz and A. Würfl
  (See online at https://doi.org/10.1002/rsa.20593)
• The approximate Loebl-Komlós-Sós conjecture (Teil I - IV). SIAM Journal on Discrete Mathematics, Volume 31, Issue 2, 945–1148
  J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein, and E. Szemerédi
  (See online at https://doi.org/10.1137/140982842)