Peter Allen, Julia Böttcher, Hiep Hàn, Yury Person, Yoshiharu Kohayakawa
We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph G is (ε,p,k,ℓ)-pseudorandom if for all disjoint X and Y⊂V(G) with |X|≥ε(pˆk)n and |Y|≥ε(pˆℓ)n we have e(X,Y)=(1±ε)p|X||Y|. We prove that for all β>0 there is an ε>0 such that an (ε,p,1,2)-pseudorandom graph on n vertices with minimum degree at least βpn contains the square of a Hamilton cycle. In particular, this implies that (n,d,λ)-graphs with λ≪(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 Szab [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403--426].
We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions.
The whole paper is available here.
Share on Twitter Share on FacebookNeuroCineMat |
---|
Featuring this week: |
Newsletter |
---|
Stay informed on our latest news! |
Follow Us on Facebook |
---|