Clique factors in pseudorandom graphs

Abstract

An $n$-vertex graph is said to to be $(p,\beta )$-bijumbled if for any vertex sets $A,B\subseteq V(G)$, we have

We prove that for any $r\in {\mathbb{N}}_{\ge 3}$ and $c>0$ there exists an $\epsilon >0$ such that any $n$-vertex $(p,\beta )$-bijumbled graph with $n\in r\mathbb{N}$, $p>0$, $\delta (G)\ge cpn$ and $\beta \le \epsilon p^{r-1}n$ contains a $K_r$-factor. This implies a corresponding result for the stronger pseudorandom notion of $(n,d,\lambda )$-graphs. For the case of triangle factors, that is, when $r=3$, this result resolves a conjecture of Krivelevich, Sudakov and Szabó from 2004 and it is tight due to a pseudorandom triangle-free construction of Alon. In fact, in this case even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition of $\beta =o(p^{2}n)$ actually guarantees that a $(p,\beta )$-bijumbled graph $G$ contains every graph on $n$ vertices with maximum degree at most 2.