Hitting-time conjecture for the Erdős–Ko–Rado property in random Kneser graphs

For integers nn and kk, let Ki(n,k)K_i(n,k) denote the random subgraph process of the Kneser graph, and define

τα=min{i:α(Ki(n,k))=(n1k1)},\tau_{\alpha}=\min\left\{i:\alpha(K_i(n,k))=\binom{n-1}{k-1}\right\}, τsuper=min{i:Ki(n,k) has no independent superstars},\tau_{\textnormal{super}}=\min\{i:K_i(n,k)\text{ has no independent superstars}\}, τnear=min{i:Ki(n,k) has no independent near-stars},\tau_{\textnormal{near}}=\min\{i:K_i(n,k)\text{ has no independent near-stars}\}, τEKR=min{i:Ki(n,k) is EKR}.\tau_{\textnormal{EKR}}=\min\{i:K_i(n,k)\text{ is EKR}\}.

Here an EKR graph is one whose maximum independent sets are precisely the stars, and a near-star is a family obtained from a star by deleting one member and adding one set outside the star. Hitting-time conjecture. With high probability, for all n>2k+1n>2k+1,

τα=τsuperandτnear=τEKR.\tau_\alpha=\tau_{\textnormal{super}}\quad\text{and}\quad\tau_{\textnormal{near}}=\tau_{\textnormal{EKR}}.

The corresponding equalities are proved in the paper when n=2k+1n=2k+1; the conjecture asserts that the hitting-time phenomenon extends to all larger values of nn and kk.

Sources & referencesView supporting material

Primary source

József Balogh, Robert A. Krueger and Haoran Luo, “Sharp threshold for the Erdős-Ko-Rado theorem”, arXiv:2105.02985 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.