## Journals

- Advances in Mathematics of Communications
- Big Data & Information Analytics
- Communications on Pure & Applied Analysis
- Discrete & Continuous Dynamical Systems - A
- Discrete & Continuous Dynamical Systems - B
- Discrete & Continuous Dynamical Systems - S
- Evolution Equations & Control Theory
- Inverse Problems & Imaging
- Journal of Computational Dynamics
- Journal of Dynamics & Games
- Journal of Geometric Mechanics
- Journal of Industrial & Management Optimization
- Journal of Modern Dynamics
- Kinetic & Related Models
- Mathematical Biosciences & Engineering
- Mathematical Control & Related Fields
- Mathematical Foundations of Computing
- Networks & Heterogeneous Media
- Numerical Algebra, Control & Optimization
- Electronic Research Announcements
- Conference Publications
- AIMS Mathematics

ERA-MS

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

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

## Year of publication

## Related Authors

## Related Keywords

[Back to Top]