TY - JOUR
T1 - Near-perfect clique-factors in sparse pseudorandom graphs
AU - Han, Jie
AU - Kohayakawa, Yoshiharu
AU - Person, Yury
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/7
Y1 - 2018/7
N2 - 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 λ≤cdt−1/nt−2 contains (1−o(1))n/t vertex-disjoint copies of Kt. 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∈3N and λ≤cd2 for a suitably small absolute constant c>0 contain triangle-factors.
AB - 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 λ≤cdt−1/nt−2 contains (1−o(1))n/t vertex-disjoint copies of Kt. 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∈3N and λ≤cd2 for a suitably small absolute constant c>0 contain triangle-factors.
KW - (n
KW - clique-factors
KW - d
KW - pseudorandomness
KW - λ)-graphs
UR - http://www.scopus.com/inward/record.url?scp=85049900713&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2018.06.038
DO - 10.1016/j.endm.2018.06.038
M3 - Article
AN - SCOPUS:85049900713
SN - 1571-0653
VL - 68
SP - 221
EP - 226
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -