The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs

Abstract

This is the second of a series of four papers in which we prove the following relaxation of the Loebl-Komlós-Sós conjecture: For every α > 0 there exists a number k0 such that for every k > k0, every n-vertex graph G with at least (1/2 + α)n vertices of degree at least (1 + α)k contains each tree T of order k as a subgraph. In the first paper of this series, we gave a decomposition of the graph G into several parts of different characteristics; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the third and fourth papers, we refine the structure and use it for embedding the tree T.