Near-perfect clique-factors in sparse pseudorandom graphs. (11th July 2021)
- Record Type:
- Journal Article
- Title:
- Near-perfect clique-factors in sparse pseudorandom graphs. (11th July 2021)
- Main Title:
- Near-perfect clique-factors in sparse pseudorandom graphs
- Authors:
- Han, Jie
Kohayakawa, Yoshiharu
Person, Yury - 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.
- Is Part Of:
- Combinatorics, probability and computing. Volume 30:Number 4(2021)
- Journal:
- Combinatorics, probability and computing
- Issue:
- Volume 30:Number 4(2021)
- Issue Display:
- Volume 30, Issue 4 (2021)
- Year:
- 2021
- Volume:
- 30
- Issue:
- 4
- Issue Sort Value:
- 2021-0030-0004-0000
- 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 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=CPC ↗
- DOI:
- 10.1017/S0963548320000577 ↗
- Languages:
- English
- ISSNs:
- 0963-5483
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library STI - ELD Digital Store
- Ingest File:
- 21759.xml