Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Tight Hamilton Cycles in Random Hypergraphs

Texto completo
Autor(es):
Allen, Peter [1] ; Boettcher, Julia [1] ; Kohayakawa, Yoshiharu [2] ; Person, Yury [3]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] London Sch Econ, Dept Math, London WC2A 2AE - England
[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[3] Goethe Univ, Inst Math, D-60325 Frankfurt - Germany
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 46, n. 3, p. 446-465, MAY 2015.
Citações Web of Science: 7
Resumo

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability p=n-1+epsilon for every epsilon>0. This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374-385), who used a second moment method to show that tight Hamilton cycles exist even for p=(n)/n(r3) where (n) arbitrary slowly, and for p=(e+o(1))/n(r4). The method we develop for proving our result applies to related problems as well. (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446-465, 2015 (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
Beneficiário:Julia Boettcher
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
Beneficiário:Peter David Allen
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
Beneficiário:Jefferson Antonio Galves
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs