Surveys in Combinatorics 2009: Embedding large subgraphs into dense graphs

By D. Kühn, Deryk Osthus. 2009

171 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/db2d5dae9a0799ff4377f2a993052e49e7f833e3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Peter Keevash
2. Richard Mycroft
3. Jie Han
4. Allan Siu Lun Lo
5. K. Markstrom

In Discrete Mathematics and Combinatorics

1. Peter Keevash
2. Richard Mycroft
3. Allan Siu Lun Lo
4. Jie Han
5. Matthew Kwan
6. Deryk Osthus
7. D. Kühn
8. Stefan Glock

In Electrical and Electronic Engineering

1. Peter Keevash
2. Richard Mycroft
3. Matthew Kwan
4. Deryk Osthus
5. D. Kühn
6. Allan Siu Lun Lo
7. Stefan Glock

Citations in the corpus

• A Geometric Theory for Hypergraph Matching (2011, methodology): “We refer the reader to their survey [32] for further results of this type.”
• Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, methodology): “We refer the reader to the surveys [119] for graphs and [161] for hypergraphs.”