# American Institute of Mathematical Sciences

2015, 22: 1-11. doi: 10.3934/era.2015.22.1

## 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, Czech Republic 2 Institute of Computer Science, Czech Academy of Sciences, Pod Vodárenskou vĕží 2, 182 07 Prague, Czech Republic 3 Rényi Institute, Budapest, Hungary 4 Centro de Modelamiento Matemático, Universidad de Chile, Beauchef 851, Santiago Centro, RM, Chile 5 Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, United States

Received  April 2014 Revised  March 2015 Published  April 2015

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].
Citation: Jan Hladký, Diana Piguet, Miklós Simonovits, Maya Stein, Endre Szemerédi. The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs. Electronic Research Announcements, 2015, 22: 1-11. doi: 10.3934/era.2015.22.1
##### 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.

show all references

##### 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.
 [1] Changfeng Gui. On some problems related to de Giorgi’s conjecture. Communications on Pure and Applied Analysis, 2003, 2 (1) : 101-106. doi: 10.3934/cpaa.2003.2.101 [2] Lingyu Jin, Yan Li. A Hopf's lemma and the boundary regularity for the fractional p-Laplacian. Discrete and Continuous Dynamical Systems, 2019, 39 (3) : 1477-1495. doi: 10.3934/dcds.2019063 [3] Uri Shapira. On a generalization of Littlewood's conjecture. Journal of Modern Dynamics, 2009, 3 (3) : 457-477. doi: 10.3934/jmd.2009.3.457 [4] Panos K. Palamides, Alex P. Palamides. Singular boundary value problems, via Sperner's lemma. Conference Publications, 2007, 2007 (Special) : 814-823. doi: 10.3934/proc.2007.2007.814 [5] Yakov Varshavsky. A proof of a generalization of Deligne's conjecture. Electronic Research Announcements, 2005, 11: 78-88. [6] Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. [7] Adriano Regis Rodrigues, César Castilho, Jair Koiller. Vortex pairs on a triaxial ellipsoid and Kimura's conjecture. Journal of Geometric Mechanics, 2018, 10 (2) : 189-208. doi: 10.3934/jgm.2018007 [8] Laurent Desvillettes, Clément Mouhot, Cédric Villani. Celebrating Cercignani's conjecture for the Boltzmann equation. Kinetic and Related Models, 2011, 4 (1) : 277-294. doi: 10.3934/krm.2011.4.277 [9] Chengzhi Li, Changjian Liu. A proof of a Dumortier-Roussarie's conjecture. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022095 [10] Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25 [11] Fabio Cipriani, Gabriele Grillo. On the $l^p$ -agmon's theory. Conference Publications, 1998, 1998 (Special) : 167-176. doi: 10.3934/proc.1998.1998.167 [12] Evangeline P. Bautista, Philippe Gaborit, Jon-Lark Kim, Judy L. Walker. s-extremal additive $\mathbb F_4$ codes. Advances in Mathematics of Communications, 2007, 1 (1) : 111-130. doi: 10.3934/amc.2007.1.111 [13] Jagmohan Tyagi, Ram Baran Verma. Positive solution to extremal Pucci's equations with singular and gradient nonlinearity. Discrete and Continuous Dynamical Systems, 2019, 39 (5) : 2637-2659. doi: 10.3934/dcds.2019110 [14] Amit Einav. On Villani's conjecture concerning entropy production for the Kac Master equation. Kinetic and Related Models, 2011, 4 (2) : 479-497. doi: 10.3934/krm.2011.4.479 [15] Jiyoung Han. Quantitative oppenheim conjecture for $S$-arithmetic quadratic forms of rank $3$ and $4$. Discrete and Continuous Dynamical Systems, 2021, 41 (5) : 2205-2225. doi: 10.3934/dcds.2020359 [16] Richard Moeckel. A proof of Saari's conjecture for the three-body problem in $\R^d$. Discrete and Continuous Dynamical Systems - S, 2008, 1 (4) : 631-646. doi: 10.3934/dcdss.2008.1.631 [17] Mario Roy. A new variation of Bowen's formula for graph directed Markov systems. Discrete and Continuous Dynamical Systems, 2012, 32 (7) : 2533-2551. doi: 10.3934/dcds.2012.32.2533 [18] Danilo Coelho, David Pérez-Castrillo. On Marilda Sotomayor's extraordinary contribution to matching theory. Journal of Dynamics and Games, 2015, 2 (3&4) : 201-206. doi: 10.3934/jdg.2015001 [19] V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413 [20] Alessandro Ferriero. A direct proof of the Tonelli's partial regularity result. Discrete and Continuous Dynamical Systems, 2012, 32 (6) : 2089-2099. doi: 10.3934/dcds.2012.32.2089

2020 Impact Factor: 0.929