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

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)64-78
Number of pages15
JournalJournal of Combinatorial Theory. Series A
Volume137
DOIs
StatePublished - Jan 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Intersecting families
  • Random graphs
  • Stability
  • Transference

Fingerprint

Dive into the research topics of 'On the stability of the Erdős-Ko-Rado theorem'. Together they form a unique fingerprint.

Cite this