Clique-factors in sparse pseudorandom graphs. (December 2019)

• Record Type: Journal Article
• Authors: Han, Jie; Kohayakawa, Yoshiharu; Morris, Patrick; Person, Yury
• Is Part Of: European journal of combinatorics. Volume 82(2019)
• Publication Date: 2019-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.102999
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We prove that for any t ≥ 3 there exist constants c > 0 and n 0 such that any d -regular n -vertex graph G with t ∣ n ≥ n 0 and second largest eigenvalue in absolute value λ satisfying λ ≤ c d t ∕ n t − 1 contains a K t -factor, that is, vertex-disjoint copies of K t covering every vertex of G . The result generalizes to broader setting of jumbled graphs, which were introduced by Thomason in the eighties.