
AbstractFor 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 .
Kneser graph, Extremal set theory, FOS: Mathematics, transference, Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.), Combinatorics (math.CO), 05C80, 05D05, 05D40, hitting time, intersecting families
Kneser graph, Extremal set theory, FOS: Mathematics, transference, Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.), Combinatorics (math.CO), 05C80, 05D05, 05D40, hitting time, intersecting families
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
