2012/11/13 by Jan Hladký, János Komlós, Hladký, Jan +9 · 1 citation
Mathematics · #05C05 (secondary) #05C35 (primary) #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #math.CO #msc:05C05 #msc:05C35
paper · pdf · doi:10.48550/arxiv.1211.3050
166 pages, 18 figures, 2 tables. This version should now be consider obsolate and is replaced by a series: [arXiv:1408.3858], [arXiv:1408.3871], [arXiv:1408.3866], [arXiv:1408.3870]. The only change compared to the previous arXiv version is this comment
openalex publication_date 2012/11/13 · arxiv created 2015/07/14 · arxiv updated 2015/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove the following version of the Loebl-Komlos-Sos Conjecture: For every alpha>0 there exists a number M such that for every k>M every n-vertex graph G with at least (0.5+alpha)n vertices of degree at least (1+alpha)k contains each tree T of order k as a subgraph. The method to prove our result follows a strategy common to approaches which employ the Szemeredi Regularity Lemma: we decompose the graph G, find a suitable combinatorial structure inside the decomposition, and then embed the tree T into G using this structure. However, the decomposition given by the Regularity Lemma is not of help when G is sparse. To surmount this shortcoming we use a more general decomposition technique: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and two other objects each exhibiting certain expansion properties.