2018/06/01 by Han, Jie, Kohayakawa, Yoshiharu, Person, Yury
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.00493
We prove that, for any t≥ 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~λ satisfying λ≤ c dt-1/nt-2 contains vertex-disjoint copies of Kt covering all but at most n1-1/(8t4) vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), pp.~403--426] that (n,d,λ)-graphs with n∈ 3ℕ and λ≤ cd2/n for a suitably small absolute constant~c>0 contain triangle-factors.