A blow-up lemma for approximate decompositions

DOI10.1090/tran/7411zbMath1409.05114arXiv1604.07282OpenAlexW2962829515WikidataQ124982694 ScholiaQ124982694MaRDI QIDQ4633567

Daniela Kühn, Mykhaylo Tyomkyn, Deryk Osthus, Jae-Hoon Kim

Publication date: 3 May 2019

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

dense graphsapproximate decomposition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of packing and covering (05B40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Density (toughness, etc.) (05C42)

Related Items (22)

Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree ⋮ The generalised Oberwolfach problem ⋮ A Short proof of the blow-up lemma for approximate decompositions ⋮ Packing degenerate graphs greedily ⋮ Random perfect matchings in regular graphs ⋮ Blowup polynomials and delta-matroids of graphs ⋮ Perfectly packing graphs with bounded degeneracy and many leaves ⋮ Graph and hypergraph packing ⋮ Tree decompositions of graphs without large bipartite holes ⋮ Almost all trees are almost graceful ⋮ A rainbow blow‐up lemma ⋮ Embedding rainbow trees with applications to graph labelling and decomposition ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ A proof of Ringel's conjecture ⋮ Optimal packings of bounded degree trees ⋮ Long path and cycle decompositions of even hypercubes ⋮ Resolution of the Oberwolfach problem ⋮ Packing trees of unbounded degrees in random graphs ⋮ Decomposing Graphs into Edges and Triangles ⋮ Packing and covering directed triangles asymptotically ⋮ Pseudorandom hypergraph matchings ⋮ Packing degenerate graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximate version of the tree packing conjecture
• Packing minor-closed families of graphs into complete graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Complete solutions to the Oberwolfach problem for an infinite set of orders
• Packing trees in complete graphs
• Proof of the Seymour conjecture for large graphs
• Blow-up lemma
• Perfect matchings in \(\varepsilon\)-regular graphs
• Every \(H\)-decomposition of \(K_n\) has a nearly resolvable alternative
• Some remarks on packing trees
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• The minimum degree threshold for perfect graph packings
• Packing large trees of consecutive orders
• Hamilton decompositions of regular expanders: applications
• Packing \(d\)-degenerate graphs
• Packing spanning graphs from separable families
• Spanning Trees in Dense Graphs
• Packing Trees into the Complete Graph
• Asymptotic Existence of Resolvable Graph Designs
• The Hamilton-Waterloo problem: The case of triangle-factors and one Hamilton cycle
• Embedding large subgraphs into dense graphs
• The Algorithmic Aspects of the Regularity Lemma
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Cycle decompositions V: Complete graphs into cycles of arbitrary lengths
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• On the Tree Packing Conjecture
• On the Bollobás–Eldridge Conjecture for Bipartite Graphs
• Optimal path and cycle decompositions of dense quasirandom graphs
• Edge-decompositions of graphs with high minimum degree
• Proof of the Alon-Yuster conjecture

This page was built for publication: A blow-up lemma for approximate decompositions