Electronic Research Announcements in Mathematical Sciences (ERA-MS)

The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

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

       Abstract        References        Full Text (423.3K)              Related Articles       

Jan Hladký - Institute of Mathematics, Czech Academy of Science, Žitná 25, 110 00, Praha, Czech Republic (email)
Diana Piguet - Institute of Computer Science, Czech Academy of Sciences, Pod Vodárenskou vĕží 2, 182 07 Prague, Czech Republic (email)
Miklós Simonovits - Rényi Institute, Budapest, Hungary (email)
Maya Stein - Centro de Modelamiento Matemático, Universidad de Chile, Beauchef 851, Santiago Centro, RM, Chile (email)
Endre Szemerédi - Department of Mathematics, Rutgers University, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, United States (email)

Abstract: 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].

Keywords:  Extremal graph theory, tree-containment problems, Loebl-Komlós-Sós conjecture, regularity lemma, sparse graphs.
Mathematics Subject Classification:  05C35 (primary), 05C05 (secondary).

Received: April 2014;      Revised: March 2015;      Available Online: April 2015.