The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition

Abstract

In a series of four papers we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For every $\alpha >0$ there exists a number $k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac{1}{2}+\alpha )n$ vertices of degree at least $(1+\alpha )k$ contains each tree $T$ of order $k$ as a subgraph. The method to prove our result follows a strategy similar to approaches that employ the Szemerédi regularity lemma: we decompose the graph $G$, find a suitable combinatorial structure inside the decomposition, and then embed the tree $T$ into $G$ using this structure. Since for sparse graphs $G$, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. In this paper, we introduce this novel decomposition technique. In the three follow-up papers, we find a combinatorial structure suitable inside the decomposition, which we then use for embedding the tree.

41 pages, 6 figures; further referees' comments incorporated, the most substantial of which being a newly written Section 3.8

References in corpus (4)

• The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result
• The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
• The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs
• The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs

Cited by in corpus (6)

• The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result
• A Variant of the Erdős-Sós Conjecture
• The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
• The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs