Near-perfect clique-factors in sparse pseudorandom graphs

Jie Han; Yoshiharu Kohayakawa; Yury Person

doi:10.1016/j.endm.2018.06.038

Near-perfect clique-factors in sparse pseudorandom graphs

Jie Han
, Yoshiharu Kohayakawa
, Yury Person

Universidade de São Paulo
Ilmenau University of Technology

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

6 Citations (Scopus)

Abstract

We prove that, for any t≥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 λ≤cd^t−1/n^t−2 contains (1−o(1))n/t vertex-disjoint copies of K_t. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), pp. 403–426] that (n,d,λ)-graphs with n∈3N and λ≤cd² for a suitably small absolute constant c>0 contain triangle-factors.

Original language	English
Pages (from-to)	221-226
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	68
DOIs	https://doi.org/10.1016/j.endm.2018.06.038
Publication status	Published - Jul 2018
Externally published	Yes

Keywords

(n
clique-factors
d
pseudorandomness
λ)-graphs

Access to Document

10.1016/j.endm.2018.06.038

Cite this

@article{718dea6f6cf742ae8d62d6bed353f279,

title = "Near-perfect clique-factors in sparse pseudorandom graphs",

abstract = "We prove that, for any t≥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 λ≤cdt−1/nt−2 contains (1−o(1))n/t vertex-disjoint copies of Kt. This provides further support for the conjecture of Krivelevich, Sudakov and Sz{\'a}bo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), pp. 403–426] that (n,d,λ)-graphs with n∈3N and λ≤cd2 for a suitably small absolute constant c>0 contain triangle-factors.",

keywords = "(n, clique-factors, d, pseudorandomness, λ)-graphs",

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

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = jul,

doi = "10.1016/j.endm.2018.06.038",

language = "English",

volume = "68",

pages = "221--226",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Near-perfect clique-factors in sparse pseudorandom graphs

AU - Han, Jie

AU - Kohayakawa, Yoshiharu

AU - Person, Yury

PY - 2018/7

Y1 - 2018/7

N2 - We prove that, for any t≥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 λ≤cdt−1/nt−2 contains (1−o(1))n/t vertex-disjoint copies of Kt. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), pp. 403–426] that (n,d,λ)-graphs with n∈3N and λ≤cd2 for a suitably small absolute constant c>0 contain triangle-factors.

AB - We prove that, for any t≥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 λ≤cdt−1/nt−2 contains (1−o(1))n/t vertex-disjoint copies of Kt. This provides further support for the conjecture of Krivelevich, Sudakov and Szábo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), pp. 403–426] that (n,d,λ)-graphs with n∈3N and λ≤cd2 for a suitably small absolute constant c>0 contain triangle-factors.

KW - (n

KW - clique-factors

KW - d

KW - pseudorandomness

KW - λ)-graphs

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

U2 - 10.1016/j.endm.2018.06.038

DO - 10.1016/j.endm.2018.06.038

M3 - Article

AN - SCOPUS:85049900713

SN - 1571-0653

VL - 68

SP - 221

EP - 226

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Near-perfect clique-factors in sparse pseudorandom graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this