Sharp threshold for the Erdős–Ko–Rado theorem. Issue 1 (16th April 2022)

• Record Type: Journal Article
• Authors: Balogh, József; Krueger, Robert A.; Luo, Haoran
• Is Part Of: Random structures & algorithms. Volume 62:Issue 1(2023)
• Page Start: 3
• Page End: 28
• Publication Date: 2022-04-16
• Subjects: hitting time -- intersecting families -- Kneser graph -- transference; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21090
• Languages: English
• ISSNs: 1042-9832

Abstract

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, \dots, 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 $$ .