Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655203 | Journal of Combinatorial Theory, Series A | 2016 | 15 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Béla Bollobás, Bhargav P. Narayanan, Andrei M. Raigorodskii,