Hamilton cycles in graphs and hypergraphs: an extremal perspective

Abstract

As one of the most fundamental and well-known NP-complete problems, the Hamilton cycle problem has been the subject of intensive research. Recent developments in the area have highlighted the crucial role played by the notions of expansion and quasi-randomness. These concepts and other recent techniques have led to the solution of several long-standing problems in the area. New aspects have also emerged, such as resilience, robustness and the study of Hamilton cycles in hypergraphs. We survey these developments and highlight open problems, with an emphasis on extremal and probabilistic approaches.

to appear in the Proceedings of the ICM 2014; due to given page limits, this final version is slightly shorter than the previous arxiv version

References in corpus (6)

• Minimum vertex degree conditions for loose Hamilton cycles in $3$-uniform hypergraphs
• Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case
• Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions
• Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case
• Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
• Tight co-degree condition for the existence of loose Hamilton cycles in 3-graphs

Cited by in corpus (13)

• The existence of designs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• Bipartite Kneser graphs are Hamiltonian
• Proof of Komlós's conjecture on Hamiltonian subsets
• Matching number, Hamiltonian graphs and discrete magnetic Laplacians
• On Weak Hamiltonicity of a Random Hypergraph
• Spanning surfaces in 3-graphs
• Hamiltonian Berge cycles in random hypergraphs
• Hamiltonicity in Cherry-quasirandom 3-graphs
• Cover 3-uniform hypergraphs by vertex-disjoint tight paths
• Large $Y_{k,b}$-tilings and Hamilton $\ell$-cycles in $k$-uniform hypergraphs
• Counting Hamiltonian Cycles in Dirac Hypergraphs
• A Note on Minimum Degree Condition for Hamiltonian $(a,b)$-Cycles in Hypergraphs