Clique factors in pseudorandom graphs

  • Patrick Morris

    Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain
Clique factors in pseudorandom graphs cover

A subscription is required to access this article.

Abstract

An -vertex graph is said to to be -bijumbled if for any vertex sets , we have

We prove that for any and there exists an such that any -vertex -bijumbled graph with , , and contains a -factor. This implies a corresponding result for the stronger pseudorandom notion of -graphs. For the case of triangle factors, that is, when , 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 actually guarantees that a -bijumbled graph contains every graph on vertices with maximum degree at most 2.

Cite this article

Patrick Morris, Clique factors in pseudorandom graphs. J. Eur. Math. Soc. (2023), published online first

DOI 10.4171/JEMS/1388