Minimum degree conditions for tight Hamilton cycles

DOI10.1112/JLMS.12561zbMATH Open1519.05142arXiv2005.05291OpenAlexW3022405419MaRDI QIDQ6133938FDOQ6133938

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)

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.

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

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

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)

Cites Work

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

Cited In (17)

• Embedding loose spanning trees in 3-uniform hypergraphs
• Towards Lehel's conjecture for 4-uniform tight cycles
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Minimum implicit degree condition restricted to claws for Hamiltonian cycles
• 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
• Decomposing hypergraphs into cycle factors
• 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
• A pair degree condition for Hamiltonian cycles in 3-uniform hypergraphs
• Sufficient conditions for perfect mixed tilings
• Transversal Hamilton cycle in hypergraph systems
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• On sufficient conditions for spanning structures in dense graphs
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Large monochromatic components in colorings of complete hypergraphs

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)