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 \emph{Graph Theory, (1992), 1135. Google Scholar [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., (). Google Scholar [3] N. Alon, A. Shapira and U. Stav, Can a graph have distinct regular partitions?,, \emph{SIAM J. Discrete Math.}, 23 (): 278. doi: 10.1137/070695952. Google Scholar [4] C. Borgs, J. Chayes and L. Lovász, Moments of two-variable functions and the uniqueness of graph limits,, \emph{Geom. Func. Anal.}, 19 (2010), 1597. doi: 10.1007/s00039-010-0044-0. Google Scholar [5] S. Brandt and E. Dobson, The Erdős-Sós conjecture for graphs of girth $5$,, \emph{Discr. Math.}, 150 (1996), 411. doi: 10.1016/0012-365X(95)00207-D. Google Scholar [6] C. Bazgan, H. Li and M. Woźniak, On the Loebl-Komlós-Sós conjecture,, \emph{J. Graph Theory}, 34 (2000), 269. doi: 10.1002/1097-0118(200008)34:4<269::AID-JGT3>3.0.CO;2-Y. Google Scholar [7] O. Cooley, Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs,, \emph{Discrete Math.}, 309 (2009), 6190. doi: 10.1016/j.disc.2009.05.030. Google Scholar [8] E. Dobson, Constructing trees in graphs whose complement has no $K_{2,s}$,, \emph{Combin. Probab. Comput.}, 11 (2002), 343. doi: 10.1017/S0963548302005102. Google Scholar [9] P. Erdős, Z. Füredi, M. Loebl and V. T. Sós, Discrepancy of trees,, \emph{Studia Sci. Math. Hungar.}, 30 (1995), 47. Google Scholar [10] P. Erdős and T. Gallai, On maximal paths and circuits of graphs,, \emph{Acta Math. Acad. Sci. Hungar}, 10 (1959), 337. doi: 10.1007/BF02024498. Google Scholar [11] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems,, in \emph{Erdös Centennial}, (2013), 169. doi: 10.1007/978-3-642-39286-3_7. Google Scholar [12] L. Gerencsér and A. Gyárfás, On Ramsey-type problems,, \emph{Ann. Univ. Sci. Budapest. Eötvös Sect. Math.}, 10 (1967), 167. Google Scholar [13] P. E. Haxell, Tree embeddings,, \emph{J. Graph Theory}, 36 (2001), 121. doi: 10.1002/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U. Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [19] P. E. Haxell, T. Luczak and P. W. Tingley, Ramsey numbers for trees of small maximum degree,, \emph{Combinatorica}, 22 (2002), 287. doi: 10.1007/s004930200014. Google Scholar [20] J. Hladký and D. Piguet, Loebl-Komlós-Sós Conjecture: Dense case,, \arXiv{0805.4834}., (). Google Scholar [21] D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs,, in \emph{Surveys in Combinatorics 2009}, (2009), 137. Google Scholar [22] J. Komlós, G. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs,, \emph{Ann. Comb.}, 2 (1998), 43. doi: 10.1007/BF01626028. Google Scholar [23] J. Komlós, G. N. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs,, \emph{Ann. Comb.}, 2 (1998), 43. Google Scholar [24] J. Komlós, A. Shokoufandeh, M. Simonovits and E. Szemerédi, The regularity lemma and its applications in graph theory,, in \emph{Theoretical Aspects of Computer Science} (Tehran, (2000), 84. doi: 10.1007/3-540-45878-6_3. Google Scholar [25] I. Levitt, G. N. Sárközy and E. Szemerédi, How to avoid using the regularity lemma: Pósa's conjecture revisited,, \emph{Discrete Math.}, 310 (2010), 630. doi: 10.1016/j.disc.2009.05.020. Google Scholar [26] D. Piguet and M. J. Stein, The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars,, \emph{Electron. J. Combin.}, 15 (2008). Google Scholar [27] D. Piguet and M. J. Stein, An approximate version of the Loebl-Komlós-Sós conjecture,, \emph{J. Combin. Theory Ser. B}, 102 (2012), 102. doi: 10.1016/j.jctb.2011.05.002. Google Scholar [28] S. N. Soffer, The Komlós-Sós conjecture for graphs of girth 7,, \emph{Discrete Math.}, 214 (2000), 279. doi: 10.1016/S0012-365X(99)00316-7. Google Scholar [29] J.-F. Saclé and M. Woźniak, The Erdős-Sós conjecture for graphs without $C_4$,, \emph{J. Combin. Theory (Series B)}, 70 (1997), 367. doi: 10.1006/jctb.1997.1758. Google Scholar [30] E. Szemerédi, Regular partitions of graphs,, in \emph{Problèmes Combinatoires et Théorie des Graphes} (Colloq. Internat. CNRS, (1976), 399. Google Scholar [31] M. Woźniak, On the Erdős-Sós conjecture,, \emph{J. Graph Theory}, 21 (1996), 229. doi: 10.1002/(SICI)1097-0118(199602)21:2<229::AID-JGT13>3.3.CO;2-2. Google Scholar [32] Y. Zhao, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$,, \emph{Electron. J. Combin.}, 18 (2011). Google Scholar

show all references

References:
 [1] M. Ajtai, J. Komlós and E. Szemerédi, On a conjecture of Loebl,, in \emph{Graph Theory, (1992), 1135. Google Scholar [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., (). Google Scholar [3] N. Alon, A. Shapira and U. Stav, Can a graph have distinct regular partitions?,, \emph{SIAM J. Discrete Math.}, 23 (): 278. doi: 10.1137/070695952. Google Scholar [4] C. Borgs, J. Chayes and L. Lovász, Moments of two-variable functions and the uniqueness of graph limits,, \emph{Geom. Func. Anal.}, 19 (2010), 1597. doi: 10.1007/s00039-010-0044-0. Google Scholar [5] S. Brandt and E. Dobson, The Erdős-Sós conjecture for graphs of girth $5$,, \emph{Discr. Math.}, 150 (1996), 411. doi: 10.1016/0012-365X(95)00207-D. Google Scholar [6] C. Bazgan, H. Li and M. Woźniak, On the Loebl-Komlós-Sós conjecture,, \emph{J. Graph Theory}, 34 (2000), 269. doi: 10.1002/1097-0118(200008)34:4<269::AID-JGT3>3.0.CO;2-Y. Google Scholar [7] O. Cooley, Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs,, \emph{Discrete Math.}, 309 (2009), 6190. doi: 10.1016/j.disc.2009.05.030. Google Scholar [8] E. Dobson, Constructing trees in graphs whose complement has no $K_{2,s}$,, \emph{Combin. Probab. Comput.}, 11 (2002), 343. doi: 10.1017/S0963548302005102. Google Scholar [9] P. Erdős, Z. Füredi, M. Loebl and V. T. Sós, Discrepancy of trees,, \emph{Studia Sci. Math. Hungar.}, 30 (1995), 47. Google Scholar [10] P. Erdős and T. Gallai, On maximal paths and circuits of graphs,, \emph{Acta Math. Acad. Sci. Hungar}, 10 (1959), 337. doi: 10.1007/BF02024498. Google Scholar [11] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems,, in \emph{Erdös Centennial}, (2013), 169. doi: 10.1007/978-3-642-39286-3_7. Google Scholar [12] L. Gerencsér and A. Gyárfás, On Ramsey-type problems,, \emph{Ann. Univ. Sci. Budapest. Eötvös Sect. Math.}, 10 (1967), 167. Google Scholar [13] P. E. Haxell, Tree embeddings,, \emph{J. Graph Theory}, 36 (2001), 121. doi: 10.1002/1097-0118(200103)36:3<121::AID-JGT1000>3.0.CO;2-U. Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [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}., (). Google Scholar [19] P. E. Haxell, T. Luczak and P. W. Tingley, Ramsey numbers for trees of small maximum degree,, \emph{Combinatorica}, 22 (2002), 287. doi: 10.1007/s004930200014. Google Scholar [20] J. Hladký and D. Piguet, Loebl-Komlós-Sós Conjecture: Dense case,, \arXiv{0805.4834}., (). Google Scholar [21] D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs,, in \emph{Surveys in Combinatorics 2009}, (2009), 137. Google Scholar [22] J. Komlós, G. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs,, \emph{Ann. Comb.}, 2 (1998), 43. doi: 10.1007/BF01626028. Google Scholar [23] J. Komlós, G. N. Sárközy and E. Szemerédi, Proof of the Seymour conjecture for large graphs,, \emph{Ann. Comb.}, 2 (1998), 43. Google Scholar [24] J. Komlós, A. Shokoufandeh, M. Simonovits and E. Szemerédi, The regularity lemma and its applications in graph theory,, in \emph{Theoretical Aspects of Computer Science} (Tehran, (2000), 84. doi: 10.1007/3-540-45878-6_3. Google Scholar [25] I. Levitt, G. N. Sárközy and E. Szemerédi, How to avoid using the regularity lemma: Pósa's conjecture revisited,, \emph{Discrete Math.}, 310 (2010), 630. doi: 10.1016/j.disc.2009.05.020. Google Scholar [26] D. Piguet and M. J. Stein, The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars,, \emph{Electron. J. Combin.}, 15 (2008). Google Scholar [27] D. Piguet and M. J. Stein, An approximate version of the Loebl-Komlós-Sós conjecture,, \emph{J. Combin. Theory Ser. B}, 102 (2012), 102. doi: 10.1016/j.jctb.2011.05.002. Google Scholar [28] S. N. Soffer, The Komlós-Sós conjecture for graphs of girth 7,, \emph{Discrete Math.}, 214 (2000), 279. doi: 10.1016/S0012-365X(99)00316-7. Google Scholar [29] J.-F. Saclé and M. Woźniak, The Erdős-Sós conjecture for graphs without $C_4$,, \emph{J. Combin. Theory (Series B)}, 70 (1997), 367. doi: 10.1006/jctb.1997.1758. Google Scholar [30] E. Szemerédi, Regular partitions of graphs,, in \emph{Problèmes Combinatoires et Théorie des Graphes} (Colloq. Internat. CNRS, (1976), 399. Google Scholar [31] M. Woźniak, On the Erdős-Sós conjecture,, \emph{J. Graph Theory}, 21 (1996), 229. doi: 10.1002/(SICI)1097-0118(199602)21:2<229::AID-JGT13>3.3.CO;2-2. Google Scholar [32] Y. Zhao, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$,, \emph{Electron. J. Combin.}, 18 (2011). Google Scholar
 [1] Changfeng Gui. On some problems related to de Giorgi’s conjecture. Communications on Pure & 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 & Continuous Dynamical Systems - A, 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] Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25 [8] Laurent Desvillettes, Clément Mouhot, Cédric Villani. Celebrating Cercignani's conjecture for the Boltzmann equation. Kinetic & Related Models, 2011, 4 (1) : 277-294. doi: 10.3934/krm.2011.4.277 [9] 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 [10] 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 [11] Mario Roy. A new variation of Bowen's formula for graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2012, 32 (7) : 2533-2551. doi: 10.3934/dcds.2012.32.2533 [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 & Continuous Dynamical Systems - A, 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 & Related Models, 2011, 4 (2) : 479-497. doi: 10.3934/krm.2011.4.479 [15] Richard Moeckel. A proof of Saari's conjecture for the three-body problem in $\R^d$. Discrete & Continuous Dynamical Systems - S, 2008, 1 (4) : 631-646. doi: 10.3934/dcdss.2008.1.631 [16] Danilo Coelho, David Pérez-Castrillo. On Marilda Sotomayor's extraordinary contribution to matching theory. Journal of Dynamics & Games, 2015, 2 (3&4) : 201-206. doi: 10.3934/jdg.2015001 [17] V. Niţicâ. Journé's theorem for $C^{n,\omega}$ regularity. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 413-425. doi: 10.3934/dcds.2008.22.413 [18] Alessandro Ferriero. A direct proof of the Tonelli's partial regularity result. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 2089-2099. doi: 10.3934/dcds.2012.32.2089 [19] Yong Li, Hongren Wang, Xue Yang. Fink type conjecture on affine-periodic solutions and Levinson's conjecture to Newtonian systems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2607-2623. doi: 10.3934/dcdsb.2018123 [20] Dirk Pauly. On Maxwell's and Poincaré's constants. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 607-618. doi: 10.3934/dcdss.2015.8.607

2018 Impact Factor: 0.263