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–Koml ́os–S ́os Con-jecture: For everyα >0 there exists a numberk0such that for everyk > k0everyn-vertexgraphGwith at least (12+α)nvertices of degree at least (1 +α)kcontains each treeTof orderkas a subgraph.The method to prove our result follows a strategy similar to approaches that employ theSzemer ́edi regularity lemma: we decompose the graphG, find a suitable combinatorial structureinside the decomposition, and then embed the treeTintoGusing this structure. Since for sparsegraphsG, the decomposition given by the regularity lemma is not helpful, we usea more generaldecomposition technique. We show that each graph can be decomposed into vertices of hugedegree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibitingcertain expansion properties. In this paper, we introduce this novel decomposition technique. Inthe three follow-up papers, we find a combinatorial structure suitable inside the decomposition,which we then use for embedding the tree.