Clique-factors in sparse pseudorandom graphs

Jie Han; Yoshiharu Kohayakawa; Patrick Morris; Yury Person

doi:10.1016/j.ejc.2019.102999

Clique-factors in sparse pseudorandom graphs

Jie Han
, Yoshiharu Kohayakawa
, Patrick Morris
, Yury Person

University of Rhode Island
Universidade de São Paulo
Free University of Berlin
Berlin Mathematical School
Ilmenau University of Technology

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

Abstract

We prove that for any t≥3 there exist constants c>0 and n₀ such that any d-regular n-vertex graph G with t∣n≥n₀ and second largest eigenvalue in absolute value λ satisfying λ≤cd^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.

Original language	English
Article number	102999
Journal	European Journal of Combinatorics
Volume	82
DOIs	https://doi.org/10.1016/j.ejc.2019.102999
Publication status	Published - Dec 2019
Externally published	Yes

Access to Document

10.1016/j.ejc.2019.102999

Cite this

@article{41fa5699887b4bdb88b752c0024ac46d,

title = "Clique-factors in sparse pseudorandom graphs",

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

author = "Jie Han and Yoshiharu Kohayakawa and Patrick Morris and Yury Person",

note = "Publisher Copyright: {\textcopyright} 2019",

year = "2019",

month = dec,

doi = "10.1016/j.ejc.2019.102999",

language = "English",

volume = "82",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Clique-factors in sparse pseudorandom graphs

AU - Han, Jie

AU - Kohayakawa, Yoshiharu

AU - Morris, Patrick

AU - Person, Yury

PY - 2019/12

Y1 - 2019/12

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

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

UR - https://www.scopus.com/pages/publications/85084046142

U2 - 10.1016/j.ejc.2019.102999

DO - 10.1016/j.ejc.2019.102999

M3 - Article

AN - SCOPUS:85084046142

SN - 0195-6698

VL - 82

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 102999

ER -

Clique-factors in sparse pseudorandom graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this