The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result

Abstract

This is the last paper of a series of four papers in which 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. In the first two papers of this series, we decomposed the host graph $G$, and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure, and proved that any graph satisfying the conditions of the above approximate version of the Loebl-Komlos-Sos Conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations.

81 pages, 12 figures. A fix reflecting the change of Preconfiguration Clubs in Paper III, additional small changes

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 (9)

• 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
• 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 III: The finer structure of LKS graphs
• The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs
• Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result
• Maximum and minimum degree conditions for embedding trees
• Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Asymptotic Result