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 n2k+1 , the Kneser graph K ( n, k ) K(n, k) is the graph with vertex set consisting of all k k ‐sets of 1, …, n {1, …, n} , where two k k ‐sets are adjacent exactly when they are disjoint. The independent sets of K ( n, k ) K(n, k) 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(n, k) be a random spanning subgraph of K ( n, k ) K(n, k) 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(n, k) have the same independence number as K ( n, k ) K(n, k) 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 .