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

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 i...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2016-01, Vol.137, p.64-78
Main Authors: Bollobás, Béla, Narayanan, Bhargav P., Raigorodskii, Andrei M.
Format: Article
Language:English
Subjects:
Intersecting families
Random graphs
Stability
Transference
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2015.08.002