The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition

DOI10.1137/140982842zbMath1365.05141arXiv1408.3858OpenAlexW3101600257WikidataQ123262800 ScholiaQ123262800MaRDI QIDQ5267992

János Komlós, Endre Szemerédi, Diana Piguet, Jan Hladký, Miklós Simmonovits, Maya Jakobine Stein

Publication date: 14 June 2017

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

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

zbMATH Keywords

regularity lemmagraph decompositionextremal graph theoryLoebl-Komlós-Sós conjecturetree embeddingsparse graph

Mathematics Subject Classification ID

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

Related Items

Gaps in the saturation spectrum of trees, A version of the Loebl-Komlós-Sós conjecture for skew trees, A skew version of the Loebl-Komlós-Sós conjecture, Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result, Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result, Loebl-Komlós-Sós conjecture: dense case, Maximum and Minimum Degree Conditions for Embedding Trees, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, A Local Approach to the Erdös--Sós Conjecture, 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 approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
• Turán numbers of bipartite graphs plus an odd cycle
• A randomized embedding algorithm for trees
• Proof of the \((n/2 - n/2 - n/2)\) conjecture for large \(n\)
• An approximate version of Sumner's universal tournament conjecture
• Loebl-Komlós-Sós conjecture: dense case
• Embedding nearly-spanning bounded degree trees
• 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
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Expanding graphs contain all small trees
• The longest path in a random graph
• Hamiltonian circuits in random graphs
• The Erdös-Sós conjecture for graphs without \(C_ 4\)
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• 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
• Large bounded degree trees in expanding graphs
• Tree embeddings
• Spanning Trees in Dense Graphs
• Universality of random graphs and rainbow embedding
• Szemerédi's Regularity Lemma for Matrices and Sparse Graphs
• Embedding Spanning Trees in Random Graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Constructing Trees in Graphs whose Complement has no K_2,s
• A proof of Sumner's universal tournament conjecture for large tournaments
• Factors in random graphs
• Embedding large subgraphs into dense graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• The Algorithmic Aspects of the Regularity Lemma
• Szemerédi’s Regularity Lemma for Sparse Graphs
• [https://portal.mardi4nfdi.de/wiki/Publication:4506067 On the Loebl-Koml�s-S�s conjecture]
• [https://portal.mardi4nfdi.de/wiki/Publication:4865531 On the Erd�s-S�s conjecture]
• Expanders Are Universal for the Class of All Spanning Trees
• 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
• The size-Ramsey number of trees