The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

DOI10.3934/ERA.2015.22.1MaRDI QIDQ256345zbMATH OpenOpenAlexWikidataFDO

Authors Diana Piguet, Jan Hladký, Maya Stein, Miklós Simonovits, Endre Szemerédi

Publication date 9 March 2016

Published in Electronic Research Announcements in Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

extremal graph theoryregularity lemmasparse graphstree-containment problemsLoebl-Komlós-Sós conjecture

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Abstract: Loebl, Koml'os and S'os conjectured that every $n$-vertex graph $G$ with at least $n/2$ vertices of degree at least $k$ contains each tree $T$ of order $k+1$ as a subgraph. We give a sketch of a proof of the approximate version of this conjecture for large values of $k$. For our proof, we use a structural decomposition which can be seen as an analogue of Szemer'edi's regularity lemma for possibly very sparse graphs. With this tool, each graph can be decomposed into four parts: a set of vertices of huge degree, regular pairs (in the sense of the regularity lemma), and two other objects each exhibiting certain expansion properties. We then exploit the properties of each of the parts of $G$ to embed a given tree $T$. The purpose of this note is to highlight the key steps of our proof. Details can be found in [arXiv:1211.3050].

Recommendations

• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• Proof of the Loebl-Komlós-Sós conjecture for large, dense 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
• A version of the Loebl-Komlós-Sós conjecture for skew trees
• Embedding nearly-spanning bounded degree trees
• The approximate Loebl-Komlós-Sós conjecture IV: Embedding techniques and the proof of the main result
• On the Erd\H{o}s-S\'os conjecture for trees with bounded degree
• Tight bounds for embedding bounded degree trees
• An approximate version of the Loebl-Komlós-Sós conjecture

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 861349 (Why is no real title available?)
• scientific article; zbMATH DE number 881162 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• An approximate version of the Loebl-Komlós-Sós conjecture
• Can a graph have distinct regular partitions?
• Constructing Trees in Graphs whose Complement has no K_2,s
• Embedding large subgraphs into dense graphs
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• Loebl-Komlós-Sós conjecture: dense case
• Moments of two-variable functions and the uniqueness of graph limits
• On maximal paths and circuits of graphs
• On the Erd�s-S�s conjecture
• On the Loebl-Koml�s-S�s conjecture
• Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs
• Proof of the Seymour conjecture for large graphs
• Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
• Ramsey numbers for trees of small maximum degree
• The Erdös-Sós conjecture for graphs of girth 5
• The Erdös-Sós conjecture for graphs without \(C_ 4\)
• The Komlós conjecture for graphs of girth 7
• The Loebl-Komlós-Sós conjecture for trees of diameter 5 and for certain caterpillars
• 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
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• The history of degenerate (bipartite) extremal graph problems
• Tree embeddings

Cited in

(9)

• Strong 2-degenerate graph embeddings
• A version of the Loebl-Komlós-Sós conjecture for skew trees
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• 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
• Loebl-Komlós-Sós conjecture: dense case
• Tree decompositions of graphs without large bipartite holes

This page was built for publication: The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

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