Embedding large subgraphs into dense graphs
From MaRDI portal
Publication:3656239
zbMATH Open1182.05098arXiv0901.3541MaRDI QIDQ3656239FDOQ3656239
Publication date: 13 January 2010
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.
Full work available at URL: https://arxiv.org/abs/0901.3541
Recommendations
Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (76)
- On Perfect Matchings and Tilings in Uniform Hypergraphs
- Factors in randomly perturbed hypergraphs
- Transversal factors and spanning trees
- Embedding clique-factors in graphs with low \(\ell\)-independence number
- Optimal spread for spanning subgraphs of Dirac hypergraphs
- \(H\)-factors in graphs with small independence number
- A note on color-bias perfect matchings in hypergraphs
- Spanning subdivisions in Dirac graphs
- Triangle resilience of the square of a Hamilton cycle in random graphs
- Minimum degree conditions for containing an \(r\)-regular \(r\)-connected spanning subgraph
- Graph and hypergraph colouring via nibble methods: a survey
- Brief announcement
- A note on perfect matchings in uniform hypergraphs
- 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
- The extremal function for partial bipartite tilings
- Improved bound on vertex degree version of Erdős matching conjecture
- On Komlós’ tiling theorem in random graphs
- Degree versions of theorems on intersecting families via stability
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Hamilton decompositions of regular expanders: applications
- Spanning trees of dense directed graphs
- An approximate version of Sumner's universal tournament conjecture
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- A geometric theory for hypergraph matching
- Monochromatic cycle partitions of graphs with large minimum degree
- Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
- Cycles of given length in oriented graphs
- Permanents of multidimensional matrices: Properties and applications
- Triangle packings and 1-factors in oriented graphs
- 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
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- Tiling tripartite graphs with 3-colorable graphs: the extreme case
- Spanning trees in dense directed graphs
- 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
- A blow-up lemma for approximate decompositions
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- \(d\)-matching in 3-uniform hypergraphs
- An Asymptotic Multipartite Kühn--Osthus Theorem
- Spanning Trees with Few Branch Vertices
- Bandwidth theorem for random graphs
- Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
- Minimum Codegree Threshold forC63-Factors in 3-Uniform Hypergraphs
- Hamilton cycles in dense vertex-transitive graphs
- \(F\)-factors in hypergraphs via absorption
- Long monochromatic paths and cycles in 2-colored bipartite graphs
- Local resilience of spanning subgraphs in sparse random graphs
- Perfect Matchings in Hypergraphs and the Erdös Matching Conjecture
- A proof of Sumner's universal tournament conjecture for large tournaments
- The complexity of perfect matchings and packings in dense hypergraphs
- Rainbow factors in hypergraphs
- A spanning bandwidth theorem in random graphs
- TILING DIRECTED GRAPHS WITH TOURNAMENTS
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Hamiltonian degree sequences in digraphs
- Exact Minimum Codegree Threshold for K−4-Factors
- Embedding large graphs into a random graph
- Matching in 3-uniform hypergraphs
- Fractional and integer matchings in uniform hypergraphs
- On the KŁR conjecture in random graphs
- A hypergraph blow-up lemma
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- On sufficient conditions for spanning structures in dense graphs
- Matching of Given Sizes in Hypergraphs
- Matchings in 3-uniform hypergraphs of large minimum vertex degree
- Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
- On embedding well-separable graphs
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Forbidding Hamilton cycles in uniform hypergraphs
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)
