Powers of Hamilton cycles in pseudorandom graphs

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,\ell )$-pseudorandom if for all disjoint $X$ and $Y\subset V(G)$ with $|X|\ge \epsilon p^{k}n$ and $|Y|\ge \epsilon p^{\ell }n$ we have $e(X,Y)=(1\pm \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 \ll 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.

30 pages, 1 figure

References in corpus (2)

• Extremal results in sparse pseudorandom graphs
• Some new problems in additive combinatorics