2021/01/13 by Morris, Patrick · 1 citation
#05C35 #05C48 #05C70 #05D40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2101.05092
An n-vertex graph is said to to be (p,β)-bijumbled if for any vertex sets A,B⊆ V(G), we have e(A,B)=p|A||B|± β√(|A||B|). We prove that for any 3≤ r∈ ℕ and c>0 there exists an ε>0 such that any n-vertex (p,β)-bijumbled graph with n∈ r ℕ, δ(G)≥ cpn and β≤ ε pr-1n, contains a Kr-factor. This implies a corresponding result for the stronger pseudorandom notion of (n,d,λ)-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 β=o(p2n) actually guarantees that a (p,β)-bijumbled graph G contains every graph on n vertices with maximum degree at most 2.