Resilience for loose Hamilton cycles

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 8-pg., 2023-01-01.

Resumo

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)

• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• Processo FAPESP: 21/11020-9 - Subestruturas de grandes proporções em grafos e hipergrafos
• Beneficiário: Yoshiharu Kohayakawa
• Modalidade de apoio: Auxílio à Pesquisa - Pesquisador Visitante - Internacional
• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 20/10796-0 - Problemas estruturais em grafos aleatórios
• Beneficiário: José Diego Alvarado Morales
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado