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]

in Graph Theory, Combinatorics, and Algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, 1135-1146.  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]

Geom. Func. Anal., 19 (2010), 1597-1619. doi: 10.1007/s00039-010-0044-0.  Google Scholar

[5]

Discr. Math., 150 (1996), 411-414. doi: 10.1016/0012-365X(95)00207-D.  Google Scholar

[6]

J. Graph Theory, 34 (2000), 269-276. doi: 10.1002/1097-0118(200008)34:4<269::AID-JGT3>3.0.CO;2-Y.  Google Scholar

[7]

Discrete Math., 309 (2009), 6190-6228. doi: 10.1016/j.disc.2009.05.030.  Google Scholar

[8]

Combin. Probab. Comput., 11 (2002), 343-347. doi: 10.1017/S0963548302005102.  Google Scholar

[9]

Studia Sci. Math. Hungar., 30 (1995), 47-57.  Google Scholar

[10]

Acta Math. Acad. Sci. Hungar, 10 (1959), 337-356 (unbound insert). doi: 10.1007/BF02024498.  Google Scholar

[11]

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.  Google Scholar

[12]

Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 10 (1967), 167-170.  Google Scholar

[13]

J. Graph Theory, 36 (2001), 121-130. 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]

Combinatorica, 22 (2002), 287-320. 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]

in Surveys in Combinatorics 2009, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009, 137-167.  Google Scholar

[22]

Ann. Comb., 2 (1998), 43-60. doi: 10.1007/BF01626028.  Google Scholar

[23]

Ann. Comb., 2 (1998), 43-60.  Google Scholar

[24]

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.  Google Scholar

[25]

Discrete Math., 310 (2010), 630-641. doi: 10.1016/j.disc.2009.05.020.  Google Scholar

[26]

Electron. J. Combin., 15 (2008), Research Paper 106, 11 pp.  Google Scholar

[27]

J. Combin. Theory Ser. B, 102 (2012), 102-125. doi: 10.1016/j.jctb.2011.05.002.  Google Scholar

[28]

Discrete Math., 214 (2000), 279-283. doi: 10.1016/S0012-365X(99)00316-7.  Google Scholar

[29]

J. Combin. Theory (Series B), 70 (1997), 367-372. doi: 10.1006/jctb.1997.1758.  Google Scholar

[30]

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.  Google Scholar

[31]

J. Graph Theory, 21 (1996), 229-234. doi: 10.1002/(SICI)1097-0118(199602)21:2<229::AID-JGT13>3.3.CO;2-2.  Google Scholar

[32]

Electron. J. Combin., 18 (2011), Paper 27, 61 pp.  Google Scholar

show all references

References:
[1]

in Graph Theory, Combinatorics, and Algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, 1135-1146.  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]

Geom. Func. Anal., 19 (2010), 1597-1619. doi: 10.1007/s00039-010-0044-0.  Google Scholar

[5]

Discr. Math., 150 (1996), 411-414. doi: 10.1016/0012-365X(95)00207-D.  Google Scholar

[6]

J. Graph Theory, 34 (2000), 269-276. doi: 10.1002/1097-0118(200008)34:4<269::AID-JGT3>3.0.CO;2-Y.  Google Scholar

[7]

Discrete Math., 309 (2009), 6190-6228. doi: 10.1016/j.disc.2009.05.030.  Google Scholar

[8]

Combin. Probab. Comput., 11 (2002), 343-347. doi: 10.1017/S0963548302005102.  Google Scholar

[9]

Studia Sci. Math. Hungar., 30 (1995), 47-57.  Google Scholar

[10]

Acta Math. Acad. Sci. Hungar, 10 (1959), 337-356 (unbound insert). doi: 10.1007/BF02024498.  Google Scholar

[11]

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.  Google Scholar

[12]

Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 10 (1967), 167-170.  Google Scholar

[13]

J. Graph Theory, 36 (2001), 121-130. 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]

Combinatorica, 22 (2002), 287-320. 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]

in Surveys in Combinatorics 2009, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009, 137-167.  Google Scholar

[22]

Ann. Comb., 2 (1998), 43-60. doi: 10.1007/BF01626028.  Google Scholar

[23]

Ann. Comb., 2 (1998), 43-60.  Google Scholar

[24]

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.  Google Scholar

[25]

Discrete Math., 310 (2010), 630-641. doi: 10.1016/j.disc.2009.05.020.  Google Scholar

[26]

Electron. J. Combin., 15 (2008), Research Paper 106, 11 pp.  Google Scholar

[27]

J. Combin. Theory Ser. B, 102 (2012), 102-125. doi: 10.1016/j.jctb.2011.05.002.  Google Scholar

[28]

Discrete Math., 214 (2000), 279-283. doi: 10.1016/S0012-365X(99)00316-7.  Google Scholar

[29]

J. Combin. Theory (Series B), 70 (1997), 367-372. doi: 10.1006/jctb.1997.1758.  Google Scholar

[30]

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.  Google Scholar

[31]

J. Graph Theory, 21 (1996), 229-234. doi: 10.1002/(SICI)1097-0118(199602)21:2<229::AID-JGT13>3.3.CO;2-2.  Google Scholar

[32]

Electron. J. Combin., 18 (2011), Paper 27, 61 pp.  Google Scholar

[1]

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

[2]

Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021004

[3]

Skyler Simmons. Stability of Broucke's isosceles orbit. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3759-3779. doi: 10.3934/dcds.2021015

[4]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3241-3271. doi: 10.3934/dcds.2020404

[5]

Mikhail Dokuchaev, Guanglu Zhou, Song Wang. A modification of Galerkin's method for option pricing. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021077

[6]

Jun Tu, Zijiao Sun, Min Huang. Supply chain coordination considering e-tailer's promotion effort and logistics provider's service effort. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021062

[7]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

[8]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[9]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[10]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[11]

Kun Hu, Yuanshi Wang. Dynamics of consumer-resource systems with consumer's dispersal between patches. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021077

[12]

Yinsong Bai, Lin He, Huijiang Zhao. Nonlinear stability of rarefaction waves for a hyperbolic system with Cattaneo's law. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021049

[13]

Françoise Demengel. Ergodic pairs for degenerate pseudo Pucci's fully nonlinear operators. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3465-3488. doi: 10.3934/dcds.2021004

[14]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044

[15]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[16]

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

[17]

Maolin Cheng, Yun Liu, Jianuo Li, Bin Liu. Nonlinear Grey Bernoulli model NGBM (1, 1)'s parameter optimisation method and model application. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021054

[18]

Azeddine Elmajidi, Elhoussine Elmazoudi, Jamila Elalami, Noureddine Elalami. Dependent delay stability characterization for a polynomial T-S Carbon Dioxide model. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021035

[19]

Hideaki Takagi. Extension of Littlewood's rule to the multi-period static revenue management model with standby customers. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2181-2202. doi: 10.3934/jimo.2020064

[20]

Siqi Chen, Yong-Kui Chang, Yanyan Wei. Pseudo $ S $-asymptotically Bloch type periodic solutions to a damped evolution equation. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021017

2019 Impact Factor: 0.5

Metrics

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

[Back to Top]