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]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[2]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031

[3]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[4]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[5]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[6]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[7]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[8]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247

[9]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020267

[10]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[11]

Monia Capanna, Jean C. Nakasato, Marcone C. Pereira, Julio D. Rossi. Homogenization for nonlocal problems with smooth kernels. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020385

[12]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

[13]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[14]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[15]

Shiqiu Fu, Kanishka Perera. On a class of semipositone problems with singular Trudinger-Moser nonlinearities. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020452

[16]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018

[17]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

[18]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[19]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[20]

Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248

2019 Impact Factor: 0.5

Metrics

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

[Back to Top]