2021/05/06 by József Balogh, Robert A. Krueger, Haoran Luo · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Bayesian Methods and Mixture Models #Combinatorics #Discrete mathematics #Disjoint sets #Graph #Graph theory and applications #Induced subgraph #Limits and Structures in Graph Theory #Mathematics #Vertex (graph theory)
paper · pdf · doi:10.1002/rsa.21090
openalex publication_date 2022/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract For positive integers and with , the Kneser graph is the graph with vertex set consisting of all ‐sets of , where two ‐sets are adjacent exactly when they are disjoint. The independent sets of are ‐uniform intersecting families, and hence the maximum size independent sets are given by the Erdős–Ko–Rado Theorem. Let be a random spanning subgraph of where each edge is included independently with probability . Bollobás, Narayanan, and Raigorodskii asked for what does have the same independence number as with high probability. For , we prove a hitting time result, which gives a sharp threshold for this problem at . Additionally, completing work of Das and Tran and work of Devlin and Kahn, we determine a sharp threshold function for all .