On the stability of the Erdős-Ko-Rado theorem

Béla Bollobás; Bhargav P. Narayanan; Andrei M. Raigorodskii

doi:10.1016/j.jcta.2015.08.002

On the stability of the Erdős-Ko-Rado theorem

Béla Bollobás, Bhargav P. Narayanan, Andrei M. Raigorodskii

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

41 Scopus citations

Abstract

Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erdős-Ko-Rado theorem.

Original language	English (US)
Pages (from-to)	64-78
Number of pages	15
Journal	Journal of Combinatorial Theory. Series A
Volume	137
DOIs	https://doi.org/10.1016/j.jcta.2015.08.002
State	Published - Jan 1 2016
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Intersecting families
Random graphs
Stability
Transference

Access to Document

10.1016/j.jcta.2015.08.002

Cite this

@article{fa6731796f4f47e1bf5705152bec6eea,

title = "On the stability of the Erd{\H o}s-Ko-Rado theorem",

abstract = "Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erd{\H o}s-Ko-Rado theorem.",

keywords = "Intersecting families, Random graphs, Stability, Transference",

author = "B{\'e}la Bollob{\'a}s and Narayanan, {Bhargav P.} and Raigorodskii, {Andrei M.}",

note = "Funding Information: The first author would like to acknowledge support from EU MULTIPLEX grant 317532 and National Science Foundation grant DMS-1301614 . The second author is supported by grant 12-01-00683 of the Russian Foundation for Basic Research , grant MD-6277.2013.1 of the Russian President , and grant NSh-2519.2012.1 supporting Leading Scientific Schools of Russia . Publisher Copyright: {\textcopyright} 2015 Elsevier Inc.",

year = "2016",

month = jan,

day = "1",

doi = "10.1016/j.jcta.2015.08.002",

language = "English (US)",

volume = "137",

pages = "64--78",

journal = "Journal of Combinatorial Theory - Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - On the stability of the Erdős-Ko-Rado theorem

AU - Bollobás, Béla

AU - Narayanan, Bhargav P.

AU - Raigorodskii, Andrei M.

N1 - Funding Information: The first author would like to acknowledge support from EU MULTIPLEX grant 317532 and National Science Foundation grant DMS-1301614 . The second author is supported by grant 12-01-00683 of the Russian Foundation for Basic Research , grant MD-6277.2013.1 of the Russian President , and grant NSh-2519.2012.1 supporting Leading Scientific Schools of Russia . Publisher Copyright: © 2015 Elsevier Inc.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erdős-Ko-Rado theorem.

AB - Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erdős-Ko-Rado theorem.

KW - Intersecting families

KW - Random graphs

KW - Stability

KW - Transference

UR - http://www.scopus.com/inward/record.url?scp=84941236753&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84941236753&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2015.08.002

DO - 10.1016/j.jcta.2015.08.002

M3 - Article

AN - SCOPUS:84941236753

VL - 137

SP - 64

EP - 78

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

ER -

On the stability of the Erdős-Ko-Rado theorem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this