Resilience for loose Hamilton cycles

Author(s)

Alvarado, Jose D. ; Kohayakawa, Yoshiharu ; Lang, Richard ; Mota, Guilherme Oliveira ; Stagni, Henrique

• Document type: Journal article
• Source: XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 8-pg., 2023-01-01.

Abstract

We study the emergence of loose Hamilton cycles in subgraphs of random hypergraphs. Our main result states that the minimum d-degree threshold for loose Hamiltonicity relative to the random k-uniform hypergraph H-k(n, p) coincides with its dense analogue whenever p >= n(-(k-1)/2+o(1)). The value of p is approximately tight for d > (k + 1)/2. This is particularly interesting because the dense threshold itself is not known beyond the cases when d >= k - 2. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) (AU)

• FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Research Grants - Young Investigators Grants
• FAPESP's process: 21/11020-9 - Large substructures in random graphs and hypergraphs
• Grantee: Yoshiharu Kohayakawa
• Support Opportunities: Research Grants - Visiting Researcher Grant - International
• FAPESP's process: 19/13364-7 - Extremal and structural problems in graph theory
• Grantee: Cristina Gomes Fernandes
• Support Opportunities: Regular Research Grants
• FAPESP's process: 20/10796-0 - Structural problems in random graphs
• Grantee: José Diego Alvarado Morales
• Support Opportunities: Scholarships in Brazil - Post-Doctoral