Artículo de revista
The approximate Loebl-Komlós-Sós conjecture I: The sparse decomposition
Fecha
2017Registro en:
SIAM Journal on Discrete Mathematics, Volumen 31, Issue 2, 2017, Pages 945-982
08954801
10.1137/140982842
Autor
Hladký, Jan
Komlós, János
Piguet, Diana
Simonovits, Miklós
Stein, Maya
Szemerédi, Endre
Institución
Resumen
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.