Clique factors in pseudorandom graphs
Patrick Morris · Journal of the European Mathematical Society · 2023
An n -vertex graph is said to to be (p,\beta) -bijumbled if for any vertex sets A,B\subseteq V(G) , we have e(A,B)=p|A|\,|B|\pm \beta \sqrt{|A|\,|B|}. We prove that for any r\in {\mathbb N}_{\ge3} and c>0 there exists an \varepsilon>0 such that any n -vertex (p,\beta) -bijumbled graph with n\in r \mathbb{N} , p>0 , \delta(G)\geq cpn and \beta \leq \varepsilon 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.