Powers of Hamilton cycles in pseudorandom graphs

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.

NeuroCineMat
Featuring this week:
Newsletter

Stay informed on our latest news!



Previous issues

Podcast A Matemática do Cérebro
Podcast A Matemática do Cérebro
NeuroMat Brachial Plexus Injury Initiative
Logo of the NeuroMat Brachial Plexus Injury Initiative
Neuroscience Experiments System
Logo of the Neuroscience Experiments System
NeuroMat Parkinson Network
Logo of the NeuroMat Parkinson Network
NeuroMat's scientific-dissemination blog
Logo of the NeuroMat's scientific-dissemination blog