TY - JOUR
T1 - Near-perfect clique-factors in sparse pseudorandom graphs
AU - Han, Jie
AU - Kohayakawa, Yoshiharu
AU - Person, Yury
N1 - Publisher Copyright:
© The Author(s), 2020.
PY - 2021/7/1
Y1 - 2021/7/1
N2 - We prove that, for any, 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 contains vertex-disjoint copies of kt covering all but at most vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo (Combinatorica 24 (2004), pp. 403-426) that (n, d, λ)-graphs with n ∈ 3ℕ and for a suitably small absolute constant c > 0 contain triangle-factors. Our arguments combine tools from linear programming with probabilistic techniques, and apply them in a certain weighted setting. We expect this method will be applicable to other problems in the field.
AB - We prove that, for any, 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 contains vertex-disjoint copies of kt covering all but at most vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo (Combinatorica 24 (2004), pp. 403-426) that (n, d, λ)-graphs with n ∈ 3ℕ and for a suitably small absolute constant c > 0 contain triangle-factors. Our arguments combine tools from linear programming with probabilistic techniques, and apply them in a certain weighted setting. We expect this method will be applicable to other problems in the field.
KW - 05C35 05C48 05D40 90C35
UR - https://www.scopus.com/pages/publications/85099515814
U2 - 10.1017/S0963548320000577
DO - 10.1017/S0963548320000577
M3 - Article
AN - SCOPUS:85099515814
SN - 0963-5483
VL - 30
SP - 570
EP - 590
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
IS - 4
ER -