The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

Jan Hladký; Diana Piguet; Miklós Simonovits; Maya Stein; Endre Szemerédi

doi:10.3934/era.2015.22.1

Article Contents

2015, Volume 22: 1-11. Doi: 10.3934/era.2015.22.1 open access

This volume Previous Article Next Article Smoothing 3-dimensional polyhedral spaces

The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

1.
Institute of Mathematics, Czech Academy of Science, Žitná 25, 110 00, Praha
2.
Institute of Computer Science, Czech Academy of Sciences, Pod Vodárenskou vĕží 2, 182 07 Prague
3.
Rényi Institute, Budapest
4.
Centro de Modelamiento Matemático, Universidad de Chile, Beauchef 851, Santiago Centro, RM
5.
Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019

Received: March 31, 2014

Revised: February 28, 2015

Published: December 2014

Abstract Related Papers Cited by

Abstract

Loebl, Komlós and Sós conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$.
For our proof, we use a structural decomposition which can be seen as an analogue of Szemerédi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$.
The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050].

Keywords:

Mathematics Subject Classification: 05C35 (primary), 05C05 (secondary).

Citation:

Related Papers

Cited by

References

[1]	M. Ajtai, J. Komlós and E. Szemerédi, On a conjecture of Loebl, in Graph Theory, Combinatorics, and Algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, 1135-1146.
[2]	M. Ajtai, J. Komlós, M. Simonovits and E. Szemerédi, Proof of the Erdős-T. Sós conjecture for large trees, in preparation.
[3]	N. Alon, A. Shapira and U. Stav, Can a graph have distinct regular partitions?, SIAM J. Discrete Math., 23 (2008/09), 278-287. doi: 10.1137/070695952.
[4]	C. Borgs, J. Chayes and L. Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Func. Anal., 19 (2010), 1597-1619.doi: 10.1007/s00039-010-0044-0.
[5]	S. Brandt and E. Dobson, The Erdős-Sós conjecture for graphs of girth $5$, Discr. Math., 150 (1996), 411-414.doi: 10.1016/0012-365X(95)00207-D.
[6]	C. Bazgan, H. Li and M. Woźniak, On the Loebl-Komlós-Sós conjecture, J. Graph Theory, 34 (2000), 269-276.doi: 10.1002/1097-0118(200008)34:4<269::AID-JGT3>3.0.CO;2-Y.
[7]	O. Cooley, Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs, Discrete Math., 309 (2009), 6190-6228.doi: 10.1016/j.disc.2009.05.030.
[8]	E. Dobson, Constructing trees in graphs whose complement has no $K_{2,s}$, Combin. Probab. Comput., 11 (2002), 343-347.doi: 10.1017/S0963548302005102.
[9]	P. Erdős, Z. Füredi, M. Loebl and V. T. Sós, Discrepancy of trees, Studia Sci. Math. Hungar., 30 (1995), 47-57.
[10]	P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar, 10 (1959), 337-356 (unbound insert).doi: 10.1007/BF02024498.
[11]	Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdös Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, 169-264.doi: 10.1007/978-3-642-39286-3_7.
[12]	L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 10 (1967), 167-170.
[13]	P. E. Haxell, Tree embeddings, J. Graph Theory, 36 (2001), 121-130.doi: 10.1002/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U.
[14]	J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture, arXiv:1211.3050.
[15]	J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture I: The sparse decomposition, arXiv:1408.3858.
[16]	J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs, arXiv:1408.3871.
[17]	J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs, arXiv:1408.3866.
[18]	J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein and E. Szemerédi, The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result, arXiv:1408.3870.
[19]	P. E. Haxell, T. Luczak and P. W. Tingley, Ramsey numbers for trees of small maximum degree, Combinatorica, 22 (2002), 287-320.doi: 10.1007/s004930200014.
[20]	J. Hladký and D. Piguet, Loebl-Komlós-Sós Conjecture: Dense case, arXiv:0805.4834.
[21]	D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs, in Surveys in Combinatorics 2009, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009, 137-167.
[22]	J. Komlós, G. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb., 2 (1998), 43-60.doi: 10.1007/BF01626028.
[23]	J. Komlós, G. N. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb., 2 (1998), 43-60.
[24]	J. Komlós, A. Shokoufandeh, M. Simonovits and E. Szemerédi, The regularity lemma and its applications in graph theory, in Theoretical Aspects of Computer Science (Tehran, 2000), Lecture Notes in Comput. Sci., 2292, Springer, Berlin, 2002, 84-112.doi: 10.1007/3-540-45878-6_3.
[25]	I. Levitt, G. N. Sárközy and E. Szemerédi, How to avoid using the regularity lemma: Pósa's conjecture revisited, Discrete Math., 310 (2010), 630-641.doi: 10.1016/j.disc.2009.05.020.
[26]	D. Piguet and M. J. Stein, The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars, Electron. J. Combin., 15 (2008), Research Paper 106, 11 pp.
[27]	D. Piguet and M. J. Stein, An approximate version of the Loebl-Komlós-Sós conjecture, J. Combin. Theory Ser. B, 102 (2012), 102-125.doi: 10.1016/j.jctb.2011.05.002.
[28]	S. N. Soffer, The Komlós-Sós conjecture for graphs of girth 7, Discrete Math., 214 (2000), 279-283.doi: 10.1016/S0012-365X(99)00316-7.
[29]	J.-F. Saclé and M. Woźniak, The Erdős-Sós conjecture for graphs without $C_4$, J. Combin. Theory (Series B), 70 (1997), 367-372.doi: 10.1006/jctb.1997.1758.
[30]	E. Szemerédi, Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, CNRS, Paris, 1978, 399-401.
[31]	M. Woźniak, On the Erdős-Sós conjecture, J. Graph Theory, 21 (1996), 229-234.doi: 10.1002/(SICI)1097-0118(199602)21:2<229::AID-JGT13>3.3.CO;2-2.
[32]	Y. Zhao, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$, Electron. J. Combin., 18 (2011), Paper 27, 61 pp.