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.

[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?,, \emph{SIAM J. Discrete Math.}, 23 (): 278. doi: 10.1137/070695952.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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,, \emph{Combinatorica}, 22 (2002), 287. 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 \emph{Surveys in Combinatorics 2009}, (2009), 137.

[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.

[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.

[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.

[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.

[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).

[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.

[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.

[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.

[30]

E. Szemerédi, Regular partitions of graphs,, in \emph{Problèmes Combinatoires et Théorie des Graphes} (Colloq. Internat. CNRS, (1976), 399.

[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.

[32]

Y. Zhao, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$,, \emph{Electron. J. Combin.}, 18 (2011).

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.

[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?,, \emph{SIAM J. Discrete Math.}, 23 (): 278. doi: 10.1137/070695952.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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,, \emph{Combinatorica}, 22 (2002), 287. 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 \emph{Surveys in Combinatorics 2009}, (2009), 137.

[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.

[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.

[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.

[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.

[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).

[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.

[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.

[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.

[30]

E. Szemerédi, Regular partitions of graphs,, in \emph{Problèmes Combinatoires et Théorie des Graphes} (Colloq. Internat. CNRS, (1976), 399.

[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.

[32]

Y. Zhao, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$,, \emph{Electron. J. Combin.}, 18 (2011).

[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]

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

[3]

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

[4]

Yakov Varshavsky. A proof of a generalization of Deligne's conjecture. Electronic Research Announcements, 2005, 11: 78-88.

[5]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Aaron Hoffman, Matt Holzer. Invasion fronts on graphs: The Fisher-KPP equation on homogeneous trees and Erdős-Réyni graphs. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-24. doi: 10.3934/dcdsb.2018202

[19]

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

[20]

David Blázquez-Sanz, Juan J. Morales-Ruiz. Lie's reduction method and differential Galois theory in the complex analytic context. Discrete & Continuous Dynamical Systems - A, 2012, 32 (2) : 353-379. doi: 10.3934/dcds.2012.32.353

2016 Impact Factor: 0.483

Metrics

  • PDF downloads (13)
  • HTML views (0)
  • Cited by (0)

[Back to Top]