Sharp threshold for the Erdős–Ko–Rado theorem

József Balogh, Robert A. Krueger, Haoran Luo

Research output: Contribution to journalArticlepeer-review

Abstract

For positive integers (Formula presented.) and (Formula presented.) with (Formula presented.), the Kneser graph (Formula presented.) is the graph with vertex set consisting of all (Formula presented.) -sets of (Formula presented.), where two (Formula presented.) -sets are adjacent exactly when they are disjoint. The independent sets of (Formula presented.) are (Formula presented.) -uniform intersecting families, and hence the maximum size independent sets are given by the Erdős–Ko–Rado Theorem. Let (Formula presented.) be a random spanning subgraph of (Formula presented.) where each edge is included independently with probability (Formula presented.). Bollobás, Narayanan, and Raigorodskii asked for what (Formula presented.) does (Formula presented.) have the same independence number as (Formula presented.) with high probability. For (Formula presented.), we prove a hitting time result, which gives a sharp threshold for this problem at (Formula presented.). Additionally, completing work of Das and Tran and work of Devlin and Kahn, we determine a sharp threshold function for all (Formula presented.).

Original languageEnglish (US)
Pages (from-to)3-28
Number of pages26
JournalRandom Structures and Algorithms
Volume62
Issue number1
DOIs
StatePublished - Jan 2023

Keywords

  • Kneser graph
  • hitting time
  • intersecting families
  • transference

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Sharp threshold for the Erdős–Ko–Rado theorem'. Together they form a unique fingerprint.

Cite this