The threshold conjecture for Steiner systems in random hypergraphs

Let KknK_k^n be the complete kk-uniform hypergraph on nn vertices, let Hk(n;p)\mathcal{H}_k(n;p) be the random kk-uniform hypergraph obtained by retaining each edge independently with probability pp, and let an (n,k,k1)(n,k,k-1)-Steiner system be a collection of kk-edges in which every (k1)(k-1)-subset is contained in exactly one edge. Steiner-system threshold conjecture. The threshold for the appearance of an (n,k,k1)(n,k,k-1)-Steiner system in Hk(n;p)\mathcal{H}_k(n;p) is

Θ(lognn).\Theta\left(\frac{\log n}{n}\right).

The lower bound comes from the requirement that no facet, meaning a (k1)(k-1)-subset, remains uncovered. The conjecture is motivated by the analogous threshold for perfect matchings in hypergraphs, where the obstruction from isolated vertices determines the threshold; the paper notes that its methods only yield a much weaker upper bound.

Sources & referencesView supporting material

Primary source

Michael Simkin, “( n , k , k - 1 )-Steiner Systems in Random Hypergraphs”, arXiv:1711.01975 (2017).

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.