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)- Dirac's theorem for linear hypergraphs
- Exact minimum codegree threshold for K^-_4-factors
- A note on perfect matchings in uniform hypergraphs
- The extremal function for partial bipartite tilings
- Matchings in multipartite hypergraphs
- Improved bound on vertex degree version of Erdős matching conjecture
- Degree versions of theorems on intersecting families via stability
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Hamilton decompositions of regular expanders: applications
- An approximate version of Sumner's universal tournament conjecture
- Spanning trees of dense directed graphs
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Monochromatic cycle partitions of graphs with large minimum degree
- A geometric theory for hypergraph matching
- Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
- Perfect matchings in hypergraphs and the Erdős matching conjecture
- Cycles of given length in oriented graphs
- Triangle packings and 1-factors in oriented graphs
- Factors in randomly perturbed hypergraphs
- On factors of independent transversals in \(k\)-partite graphs
- The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs
- A degree sequence Hajnal-Szemerédi theorem
- Loebl-Komlós-Sós conjecture: dense case
- Tiling tripartite graphs with 3-colorable graphs: the extreme case
- Toward a density Corrádi-Hajnal theorem for degenerate hypergraphs
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- Spanning trees in dense directed graphs
- Matching of given sizes in hypergraphs
- Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs
- On multipartite Hajnal-Szemerédi theorems
- A multipartite Hajnal-Szemerédi theorem
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- \(d\)-matching in 3-uniform hypergraphs
- A blow-up lemma for approximate decompositions
- Transversal factors and spanning trees
- An extension of the blow-up lemma to arrangeable graphs
- Tiling directed graphs with tournaments
- On perfect packings in dense 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
- Embedding clique-factors in graphs with low -independence number
- Bandwidth theorem for random graphs
- Spanning Trees with Few Branch Vertices
- On Komlós' tiling theorem in random graphs
- Optimal spread for spanning subgraphs of Dirac hypergraphs
- Hamilton cycles in dense vertex-transitive graphs
- Recent advances on Dirac-type problems for hypergraphs
- H-factors in graphs with small independence number
- Dirac's theorem for graphs of bounded bandwidth
- Local resilience of spanning subgraphs in sparse random graphs
- \(F\)-factors in hypergraphs via absorption
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
- Long monochromatic paths and cycles in 2-colored bipartite graphs
- On perfect subdivision tilings
- Counting spanning subgraphs in dense hypergraphs
- A note on color-bias perfect matchings in hypergraphs
- Triangle resilience of the square of a Hamilton cycle in random graphs
- A proof of Sumner's universal tournament conjecture for large tournaments
- Spanning subdivisions in Dirac graphs
- The complexity of perfect matchings and packings in dense hypergraphs
- Rainbow factors in hypergraphs
- A spanning bandwidth theorem in random graphs
- On perfect matchings and tilings in uniform hypergraphs
- Minimum degree conditions for containing an \(r\)-regular \(r\)-connected spanning subgraph
- Graph and hypergraph colouring via nibble methods: a survey
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Hamiltonian degree sequences in digraphs
- Matching in 3-uniform hypergraphs
- Monochromatic cycles in 2-edge-colored bipartite graphs
- Embedding large graphs into a random graph
- On the KŁR conjecture in random graphs
- Approximate packing of independent transversals in locally sparse graphs
- An asymptotic multipartite Kühn-Osthus theorem
- Brief announcement
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
- A hypergraph blow-up lemma
- Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
- Matchings in 3-uniform hypergraphs of large minimum vertex degree
- On sufficient conditions for spanning structures in dense graphs
- On embedding well-separable graphs
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Forbidding Hamilton cycles in uniform hypergraphs
- Permanents of multidimensional matrices: properties and applications
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)
