Forbidding Hamilton cycles in uniform hypergraphs

DOI10.1016/J.JCTA.2016.05.005zbMATH Open1342.05082arXiv1508.05623OpenAlexW2201645533MaRDI QIDQ530769FDOQ530769

Authors: Jie Han, Yi Zhao 

Publication date: 1 August 2016

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

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.

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

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
• Loose Hamiltonian cycles forced by large \((k-2)\)-degree -- sharp version

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)

Cites Work

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

Cited In (14)

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

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)