Near-perfect clique-factors in sparse pseudorandom graphs. (11th July 2021)

• Record Type: Journal Article
• Authors: Han, Jie; Kohayakawa, Yoshiharu; Person, Yury
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 4(2021)
• Page Start: 570
• Page End: 590
• Publication Date: 2021-07-11
• Subjects: 05C35 -- 05C48 -- 05D40 -- 90C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000577
• Languages: English
• ISSNs: 0963-5483

Abstract

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 $\lambda \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 $\lambda \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.