2020/05/11 by Richard Lang, Lang, Richard, Nicolás Sanhueza‐Matamala +1 · 2 citations
Computer Science · Engineering · Mathematics · #05C45 #05C65 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2005.05291
openalex publication_date 2020/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Erdő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ödl, Ruciński and Szemerédi for d=k-1 by determining asymptotically best possible degree conditions for d = k-2 and all k ≥ 3. This was proved independently by Polcyn, Reiher, Rödl and Schülke. 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/√(k-d) due to Han and Zhao.