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

DOI10.3934/ERA.2015.22.1zbMATH Open1332.05074arXiv1406.3935OpenAlexW3104378477WikidataQ122973161 ScholiaQ122973161MaRDI QIDQ256345FDOQ256345

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)

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].

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

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

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)

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
• Proof of the Seymour conjecture for large 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
• Moments of two-variable functions and the uniqueness of graph limits
• Tree embeddings
• Constructing Trees in Graphs whose Complement has no K_2,s
• On maximal paths and circuits of graphs
• 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?)
• Can a graph have distinct regular partitions?
• 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
• The history of degenerate (bipartite) extremal graph problems
• 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
• How to avoid using the regularity Lemma: Pósa's conjecture revisited

Cited In (9)

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

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)