Forbidding Hamilton cycles in uniform hypergraphs

DOI10.1016/J.JCTA.2016.05.005MaRDI QIDQ530769zbMATHOpenAlexFDO

Authors Jie Han, Yi Zhao

Publication date 1 August 2016

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.05623

zbMATH Keywords

perfect matchingshypergraphsHamilton cycles

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For $1ledleell<k$, we give a new lower bound for the minimum $d$-degree threshold that guarantees a Hamilton $ell$-cycle in $k$-uniform hypergraphs. When $kge4$ and $d<ell=k-1$, this bound is larger than the conjectured minimum $d$-degree threshold for perfect matchings and thus disproves a well-known conjecture of R"odl and Ruci'nski. Our (simple) construction generalizes a construction of Katona and Kierstead and the space barrier for Hamilton cycles.

Recommendations

• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• Minimum codegree threshold for Hamilton \(\ell\)-cycles in \(k\)-uniform hypergraphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs

Cites work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Embedding large subgraphs into dense graphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Families of triples with high minimum degree are Hamiltonian
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian chains in hypergraphs
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• Loose Hamilton cycles in hypergraphs
• Minimum codegree threshold for Hamilton \(\ell\)-cycles in \(k\)-uniform hypergraphs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• On extremal hypergraphs for Hamiltonian cycles
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Perfect matchings in uniform hypergraphs with large minimum degree
• Some Theorems on Abstract Graphs
• Tight Codegree Condition for the Existence of Loose Hamilton Cycles in 3-Graphs

Cited in

(15)

• The minimum vertex degree for an almost-spanning tight cycle in a 3-uniform hypergraph
• Minimum pair-degee for tight Hamiltonian cycles in 4-uniform hypergraphs
• Hamiltonicity in cherry-quasirandom 3-graphs
• On Hamiltonian cycles in hypergraphs with dense link graphs
• Minimum degree conditions for tight Hamilton cycles
• Covering 3‐uniform hypergraphs by vertex‐disjoint tight paths
• Completion and deficiency problems
• Tight Hamilton cycles in cherry-quasirandom 3-uniform hypergraphs
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• Minimum pair degree condition for tight Hamiltonian cycles in 4-uniform hypergraphs
• On the Hamiltonicity of triple systems with high minimum degree
• Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs
• Steiner system and large non-Hamiltonian hypergraphs
• Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
• Dirac-type conditions for spanning bounded-degree hypertrees

This page was built for publication: Forbidding Hamilton cycles in uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q530769)