Abstract: What conditions ensure that a graph G contains some given spanning subgraph H? The most famous examples of results of this kind are probably Dirac's theorem on Hamilton cycles and Tutte's theorem on perfect matchings. Perfect matchings are generalized by perfect F-packings, where instead of covering all the vertices of G by disjoint edges, we want to cover G by disjoint copies of a (small) graph F. It is unlikely that there is a characterization of all graphs G which contain a perfect F-packing, so as in the case of Dirac's theorem it makes sense to study conditions on the minimum degree of G which guarantee a perfect F-packing. The Regularity lemma of Szemeredi and the Blow-up lemma of Komlos, Sarkozy and Szemeredi have proved to be powerful tools in attacking such problems and quite recently, several long-standing problems and conjectures in the area have been solved using these. In this survey, we give an outline of recent progress (with our main emphasis on F-packings, Hamiltonicity problems and tree embeddings) and describe some of the methods involved.
Recommendations
Cited in
(86)- Triangle packings and 1-factors in oriented graphs
- Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- \(d\)-matching in 3-uniform hypergraphs
- Tiling tripartite graphs with 3-colorable graphs: the extreme case
- On multipartite Hajnal-Szemerédi theorems
- On perfect packings in dense graphs
- Matching in 3-uniform hypergraphs
- Spanning trees of dense directed graphs
- Long monochromatic paths and cycles in 2-colored bipartite graphs
- Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
- The complexity of perfect matchings and packings in dense hypergraphs
- Rainbow factors in hypergraphs
- Degree versions of theorems on intersecting families via stability
- \(F\)-factors in hypergraphs via absorption
- A multipartite Hajnal-Szemerédi theorem
- Hamilton decompositions of regular expanders: applications
- The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
- A degree sequence Hajnal-Szemerédi theorem
- Triangle resilience of the square of a Hamilton cycle in random graphs
- On factors of independent transversals in \(k\)-partite graphs
- Spanning trees in dense directed graphs
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- A proof of Sumner's universal tournament conjecture for large tournaments
- Matchings in 3-uniform hypergraphs of large minimum vertex degree
- Recent advances on Dirac-type problems for hypergraphs
- Permanents of multidimensional matrices: properties and applications
- A hypergraph blow-up lemma
- Tiling directed graphs with tournaments
- Perfect matchings in hypergraphs and the Erdős matching conjecture
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- Local resilience of spanning subgraphs in sparse random graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Monochromatic cycle partitions of graphs with large minimum degree
- The extremal function for partial bipartite tilings
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Hamilton cycles in dense vertex-transitive graphs
- A blow-up lemma for approximate decompositions
- On perfect matchings and tilings in uniform hypergraphs
- On the KŁR conjecture in random graphs
- Matching of given sizes in hypergraphs
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
- On Komlós' tiling theorem in random graphs
- Spanning Trees with Few Branch Vertices
- An extension of the blow-up lemma to arrangeable graphs
- 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
- An asymptotic multipartite Kühn-Osthus theorem
- Forbidding Hamilton cycles in uniform hypergraphs
- Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- Embedding large graphs into a random graph
- Exact minimum codegree threshold for K^-_4-factors
- A geometric theory for hypergraph matching
- Transversal factors and spanning trees
- A spanning bandwidth theorem in random graphs
- Brief announcement
- Embedding clique-factors in graphs with low -independence number
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
- Factors in randomly perturbed hypergraphs
- On sufficient conditions for spanning structures in dense graphs
- Improved bound on vertex degree version of Erdős matching conjecture
- Graph and hypergraph colouring via nibble methods: a survey
- Minimum degree conditions for containing an \(r\)-regular \(r\)-connected spanning subgraph
- Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
- An approximate version of Sumner's universal tournament conjecture
- H-factors in graphs with small independence number
- Optimal spread for spanning subgraphs of Dirac hypergraphs
- A note on color-bias perfect matchings in hypergraphs
- Spanning subdivisions in Dirac graphs
- Dirac's theorem for graphs of bounded bandwidth
- Monochromatic cycles in 2-edge-colored bipartite graphs
- On perfect subdivision tilings
- Counting spanning subgraphs in dense hypergraphs
- Approximate packing of independent transversals in locally sparse graphs
- Dirac's theorem for linear hypergraphs
- Toward a density Corrádi-Hajnal theorem for degenerate hypergraphs
- Matchings in multipartite hypergraphs
- Bandwidth theorem for random graphs
- Loebl-Komlós-Sós conjecture: dense case
- A note on perfect matchings in uniform hypergraphs
- On embedding well-separable graphs
- Cycles of given length in oriented graphs
- Hamiltonian degree sequences in digraphs
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
This page was built for publication: Embedding large subgraphs into dense graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3656239)
