The approximate Loebl-Koml\'os-S\'os 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-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 \((\frac12+\alpha)n\) vertices of degree at least \((1+\alpha)k\) contains each tree \(T\) of order \(k\) as a subgraph. In the first paper of the 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 last two papers, we refine the structure and use it for embedding the tree \(T\).