Minimum degree conditions for tight Hamilton cycles

DOI10.1112/JLMS.12561MaRDI QIDQ6133938zbMATH OpenOpenAlexFDO

Authors Richard Lang, Nicolás Sanhueza-Matamala

Publication date 21 August 2023

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

minimum degreeHamilton cyclehypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65)

Abstract: We develop a new framework to study minimum $d$-degree conditions in $k$-uniform hypergraphs, which guarantee the existence of a tight Hamilton cycle. Our main theoretical result deals with the typical absorption, path cover and connecting arguments for all $k$ and $d$ at once, and thus sheds light on the underlying structural problems. Building on this, we show that one can study minimum $d$-degree conditions of $k$-uniform tight Hamilton cycles by focusing on the inner structure of the neighbourhoods. This reduces the matter to an ErdH{o}s--Gallai-type question for $(k-d)$-uniform hypergraphs, which is of independent interest. Once this framework is established, we can easily derive two new bounds. Firstly, we extend a classic result of R"odl, Ruci'nski and Szemer'edi for $d=k-1$ by determining asymptotically best possible degree conditions for $d=k-2$ and all $kge3$. This was proved independently by Polcyn, Reiher, R"odl and Sch"ulke. Secondly, we provide a general upper bound of $1-1/(2(k-d))$ for the tight Hamilton cycle $d$-degree threshold in $k$-uniform hypergraphs, thus narrowing the gap to the lower bound of $1-1/sqrtk-d$ due to Han and Zhao.

Recommendations

• Minimum vertex degree condition for tight Hamiltonian cycles in 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
• Localized codegree conditions for tight Hamilton cycles in 3-uniform hypergraphs
• On Hamiltonian cycles in hypergraphs with dense link graphs

Cites work

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3641483 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Balanced matrices
• Blow-up lemma
• Covering and tiling hypergraphs with tight cycles
• 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)
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
• Extremal problems for finite sets
• Families of triples with high minimum degree are Hamiltonian
• Forbidding Hamilton cycles in uniform hypergraphs
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamiltonian chains in hypergraphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Hypergraphs, quasi-randomness, and conditions for regularity
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• On Hamiltonian cycles in hypergraphs with dense link graphs
• On extremal hypergraphs for Hamiltonian cycles
• On the Hamiltonicity of triple systems with high minimum degree
• On the decomposition threshold of a given graph
• Recent advances on Dirac-type problems for hypergraphs
• Recent advances on the Hamiltonian problem: survey III
• Regular Partitions of Hypergraphs: Counting Lemmas
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regularity Lemma for k-uniform hypergraphs
• Some Theorems on Abstract Graphs
• The Ramsey number for 3-uniform tight hypergraph cycles
• The minimum vertex degree for an almost-spanning tight cycle in a 3-uniform hypergraph
• Tight cycles and regular slices in dense hypergraphs
• Triangle Factors in Random Graphs
• Vertex coverings by monochromatic cycles and trees
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)

Cited in

(17)

• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Minimum pair-degee for tight Hamiltonian cycles in 4-uniform hypergraphs
• On Hamiltonian cycles in hypergraphs with dense link graphs
• Embedding loose spanning trees in 3-uniform hypergraphs
• Decomposing hypergraphs into cycle factors
• Towards Lehel's conjecture for 4-uniform tight cycles
• Transversal Hamilton cycle in hypergraph systems
• Minimum implicit degree condition restricted to claws for Hamiltonian cycles
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• Minimum pair degree condition for tight Hamiltonian cycles in 4-uniform hypergraphs
• Sufficient conditions for perfect mixed tilings
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs
• Large monochromatic components in colorings of complete hypergraphs
• A pair degree condition for Hamiltonian cycles in 3-uniform hypergraphs
• Dirac-type conditions for spanning bounded-degree hypertrees
• On sufficient conditions for spanning structures in dense graphs

This page was built for publication: Minimum degree conditions for tight Hamilton cycles

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