Near-perfect clique-factors in sparse pseudorandom graphs

Abstract

We prove that, for any $t\ge 3$, there exists a constant $c=c(t)>0$ such that any $d$-regular $n$-vertex graph with the second largest eigenvalue in absolute value~$\lambda$ satisfying $\lambda \le c{d}^{t-1}/n^{t-2}$ contains vertex-disjoint copies of $K_t$ covering all but at most $n^{1-1/(8t^4)}$ vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo [\emph{Triangle factors in sparse pseudo-random graphs}, Combinatorica \textbf{24} (2004), pp.~403--426] that $(n,d,\lambda )$-graphs with $n\in 3\mathbb{N}$ and $\lambda \le c{d}^2/n$ for a suitably small absolute constant~$c>0$ contain triangle-factors.

References in corpus (1)

• Triangle-factors in pseudorandom graphs

Cited by in corpus (3)

• Finding any given 2-factor in sparse pseudorandom graphs efficiently
• On Perfect Matchings in $k$-complexes
• Rainbow perfect matchings for 4-uniform hypergraphs