Full text  
Author(s): 
Allen, Peter
;
Bottcher, Julia
;
Han, Hiep
;
Kohayakawa, Yoshiharu
;
Person, Yury
Total Authors: 5

Document type:  Journal article 
Source:  COMBINATORICA; v. 37, n. 4, p. 573616, AUG 2017. 
Web of Science Citations:  2 
Abstract  
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)pXY. 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)  
FAPESP's process:  13/034476  Combinatorial structures, optimization, and algorithms in theoretical Computer Science 
Grantee:  Carlos Eduardo Ferreira 
Support type:  Research Projects  Thematic Grants 
FAPESP's process:  09/178317  Embedding and packing problems in extremal graph theory 
Grantee:  Julia Boettcher 
Support type:  Scholarships in Brazil  PostDoctorate 
FAPESP's process:  10/095557  Embedding, randomised and structural problems in extremal graph theory 
Grantee:  Peter David Allen 
Support type:  Scholarships in Brazil  PostDoctorate 
FAPESP's process:  13/076990  Research, Innovation and Dissemination Center for Neuromathematics  NeuroMat 
Grantee:  Jefferson Antonio Galves 
Support type:  Research Grants  Research, Innovation and Dissemination Centers  RIDC 
FAPESP's process:  10/165263  Quasirandom hypergraphs and spanning subhypergraph containment 
Grantee:  Hiep Han 
Support type:  Scholarships in Brazil  PostDoctorate 