Sharp threshold for the Erdős–Ko–Rado theorem. Issue 1 (16th April 2022) - Balogh, József; Krueger, Robert A.; Luo, Haoran
Abstract: For positive integers n $$ n $$ and k $$ k $$ with n ≥ 2 k + 1 $$ n\ge 2k+1 $$, the Kneser graph K ( n, k ) $$ K\left(n, k\right) $$ is the graph with vertex set consisting of all k $$ k $$ ‐sets of { 1, …, n } $$ \left\{1, …, n\right\} $$, where two k $$ k $$ ‐sets are adjacent exactly when they are disjoint. The independent sets of K ( n, k ) $$ K\left(n, k\right) $$ are k $$ k $$ ‐uniform intersecting families, and hence the maximum size independent sets are given by the Erdős–Ko–Rado Theorem. Let K p ( n, k ) $$ K_p\left(n, k\right) $$ be a random spanning subgraph of K ( n, k ) $$ K\left(n, k\right) $$ where each edge is included independently with probability p $$ p $$ . Bollobás, Narayanan, and Raigorodskii asked for what p $$ p $$ does K p ( n, k ) $$ K_p\left(n, k\right) $$ have the same independence number as K ( n, k ) $$ K\left(n, k\right) $$ with high probability. For n = 2 k + 1 $$ n=2k+1 $$, we prove a hitting time result, which gives a sharp threshold for this problem at p = 3 / 4 $$ 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 > 2 k + 1 $$ n>2k+1 $$ .