POWERS OF HAMILTON CYCLES IN PSEUDORANDOM GRAPHS

Autor(es)

Allen, Peter ; Bottcher, Julia ; Han, Hiep ; Kohayakawa, Yoshiharu ; Person, Yury

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICA; v. 37, n. 4, p. 573-616, AUG 2017.
• Citações Web of Science: 2

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,l)-pseudorandom if for all disjoint X and Y subset of V(G) with |X|>= epsilon p(n)(k) 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 {[}27]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions. (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: 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
• 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: 10/16526-3 - Hipergrafos quase-aleatórios e imersão de subhipergrafos geradores
• Beneficiário: Hiep Han
• Linha de fomento: Bolsas no Brasil - Pós-Doutorado
• 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