Sharp threshold for the Erd\H{o}s-Ko-Rado theorem.

2021 
For positive integers $n$ and $k$ with $n\geq 2k+1$, the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$-sets of $\{1,\dots,n\}$, where two $k$-sets are adjacent exactly when they are disjoint. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$. Bollob\'as, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. For $n=2k+1$, we prove a hitting time result, which gives a sharp threshold for this problem at $p=3/4$. Additionally, completing work of Das and Tran and work of Devlin and Kahn, we determine a sharp threshold function for all $n>2k+1$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    20
    References
    0
    Citations
    NaN
    KQI
    []