Near-perfect clique-factors in sparse pseudorandom graphs. (11th July 2021) - Han, Jie; Kohayakawa, Yoshiharu; Person, Yury
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 λ satisfying $λ \le c{d^{t - 1}}/{n^{t - 2}}$ contains vertex-disjoint copies of k t covering all but at most ${n^{1 - 1/(8{t^4})}}$ 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 $λ \le c{d^2}/n$ 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.