Back to Search Start Over

The Approximate Loebl-Koml\'os-S\'os Conjecture III: The finer structure of LKS graphs

Authors :
Hladký, Jan
Komlós, János
Piguet, Diana
Simonovits, Miklós
Stein, Maya J.
Szemerédi, Endre
Source :
SIAM J. Discrete Math. 31 (2017), no. 2, 1017-1071
Publication Year :
2014

Abstract

This is the third 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. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the forthcoming fourth paper, the refined structure will be used for embedding the tree $T$.<br />Comment: 59 pages, 4 figures; further comments by a referee incorporated; this includes a subtle but important fix to Lemma 5.1; as a consequence, Preconfiguration Clubs was changed

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
SIAM J. Discrete Math. 31 (2017), no. 2, 1017-1071
Publication Type :
Report
Accession number :
edsarx.1408.3866
Document Type :
Working Paper
Full Text :
https://doi.org/10.1137/140982866