On "stability" in the Erdös-ko-Rado theorem

Pat Devlin, Jeff Kahn

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

Denote by Kp(n, k) the random subgraph of the usual Kneser graph K(n; k) in which edges appear independently, each with probability p. Answering a question of Bollobás, Narayanan, and Raigorodskii, we show that there is a fixed p < 1 such that a.s. (i.e., with probability tending to 1 as k →∞) the maximum independent sets of Kp(2k + 1, k) are precisely the sets {A ϵ V (K(2k + 1, k)) : x ϵ A} (x ϵ [2k + 1]). We also complete the determination of the order of magnitude of the "threshold" for the above property for general k and n ≥ 2k + 2. This is new for k ≥ n=2, while for smaller k it is a recent result of Das and Tran.

Original languageEnglish (US)
Pages (from-to)1283-1289
Number of pages7
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number2
DOIs
StatePublished - 2016

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Erdös-ko-rado theorem
  • Kneser graph
  • Random subgraph
  • Threshold

Fingerprint Dive into the research topics of 'On "stability" in the Erdös-ko-Rado theorem'. Together they form a unique fingerprint.

Cite this