Busca avançada
Ano de início
Entree


Powers of Hamilton Cycles in Pseudorandom Graphs

Texto completo
Autor(es):
Allen, Peter ; Boettcher, Julia ; Han, Hiep ; Kohayakawa, Yoshiharu ; Person, Yury ; Pardo, A ; Viola, A
Número total de Autores: 7
Tipo de documento: Artigo Científico
Fonte: LATIN 2014: THEORETICAL INFORMATICS; v. 8392, p. 12-pg., 2014-01-01.
Resumo

We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph G is (epsilon, p, k, F)- pseudorandom if for all disjoint X, Y subset of (G) with |X|. Spkn and |Y| >= epsilon p(l)n we have e(X, Y) = (1 +/- epsilon) p| X||Y |. We prove that for all beta > 0 there is an epsilon > 0 such that an (epsilon, p, 1, 2)- pseudorandom graph on n vertices with minimum degree at least beta pn contains the square of a Hamilton cycle. In particular, this implies that (n, d, lambda)- graphs with lambda << d(5/2)n(-3/2) contain the square of a Hamilton cycle, and thus a triangle factor if n is a multiple of 3. This improves on a result of Krivelevich, Sudakov and Szabo [Triangle factors in sparse pseudo- random graphs, Combinatorica 24 (2004), no. 3, 403-426]. We also obtain results for higher powers of Hamilton cycles and establish corresponding counting versions. Our proofs are constructive, and yield deterministic polynomial time algorithms. (AU)

Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
Beneficiário:Julia Boettcher
Modalidade de apoio: 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:Oswaldo Baffa Filho
Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
Processo FAPESP: 10/16526-3 - Hipergrafos quase-aleatórios e imersão de subhipergrafos geradores
Beneficiário:Hiep Han
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
Beneficiário:Peter David Allen
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado