The approximate Loebl-Komlós-Sós conjecture II: The rough structure of LKS graphs

DOI10.1137/140982854zbMATH Open1365.05142arXiv1408.3871OpenAlexW3102494729WikidataQ122992720 ScholiaQ122992720MaRDI QIDQ5267993FDOQ5267993

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: This is the second 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; this decomposition might be viewed as an analogue of a regular partition for sparse graphs. In the present paper, we find a combinatorial structure inside this decomposition. In the last two papers, we refine the structure and use it for embedding the tree $T$.

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

Recommendations

• 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 and embedding trees in sparse graphs
• The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
• An approximate version of the Loebl-Komlós-Sós conjecture

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) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• Embedding large subgraphs into dense graphs
• 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
• 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
• Title not available (Why is that?)

Cited In (15)

• 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
• 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 II: The rough structure of LKS graphs

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