The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition

DOI10.1137/140982842zbMATH Open1365.05141arXiv1408.3858OpenAlexW3101600257WikidataQ123262800 ScholiaQ123262800MaRDI QIDQ5267992FDOQ5267992

Authors: Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya Stein, Endre Szemerédi 

Publication date: 14 June 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: In a series of four papers 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. The method to prove our result follows a strategy similar to approaches that employ the Szemer'edi 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. Since for sparse graphs $G$, the decomposition given by the regularity lemma is not helpful, we use a more general decomposition technique. We show that 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. In this paper, we introduce this novel decomposition technique. In the three follow-up papers, we find a combinatorial structure suitable inside the decomposition, which we then use for embedding the tree.

Full work available at URL: https://arxiv.org/abs/1408.3858

Recommendations

• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• Loebl-Komlós-Sós conjecture: dense case

zbMATH Keywords

extremal graph theoryregularity lemmagraph decompositiontree embeddingsparse graphLoebl-Komlós-Sós conjecture

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars
• Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs
• The Erdös-Sós conjecture for graphs without \(C_ 4\)
• Ramsey numbers for trees of small maximum degree
• The Erdös-Sós conjecture for graphs of girth 5
• The Komlós conjecture for graphs of girth 7
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• Tree embeddings
• Tight bounds for embedding bounded degree trees
• Constructing Trees in Graphs whose Complement has no K_2,s
• Embedding large subgraphs into dense graphs
• Title not available (Why is that?)
• On the Loebl-Koml�s-S�s conjecture
• On the Erd�s-S�s conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• Title not available (Why is that?)
• An approximate version of the Loebl-Komlós-Sós conjecture
• Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
• Loebl-Komlós-Sós conjecture: dense case
• Embedding nearly-spanning bounded degree trees
• Expanding graphs contain all small trees
• Large bounded degree trees in expanding graphs
• Title not available (Why is that?)
• Factors in random graphs
• The size-Ramsey number of trees
• Hamiltonian circuits in random graphs
• Title not available (Why is that?)
• Embedding spanning trees in random graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• A proof of Sumner's universal tournament conjecture for large tournaments
• Title not available (Why is that?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Turán numbers of bipartite graphs plus an odd cycle
• The longest path in a random graph
• An approximate version of Sumner's universal tournament conjecture
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Expanders Are Universal for the Class of All Spanning Trees
• The Algorithmic Aspects of the Regularity Lemma
• Title not available (Why is that?)
• A randomized embedding algorithm for trees
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• On the Loebl-Komlós-Sós conjecture
• Spanning trees in dense graphs
• Universality of random graphs and rainbow embedding

Cited In (16)

• Maximum and minimum degree conditions for embedding trees
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
• Gaps in the saturation spectrum of trees
• A version of the Loebl-Komlós-Sós conjecture for skew trees
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• Loebl-Komlós-Sós conjecture: dense case
• A blow-up lemma for approximate decompositions
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture III: The finer structure of LKS graphs
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• Embedding trees with maximum and minimum degree conditions
• Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
• A skew version of the Loebl-Komlós-Sós conjecture
• A Local Approach to the Erdös--Sós Conjecture

This page was built for publication: The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5267992)