The threshold conjecture for Steiner systems in random hypergraphs

About 9 years old · traced to

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,k−1)(n,k,k-1)-Steiner system be a collection of kk-edges in which every (k−1)(k-1)-subset is contained in exactly one edge. Steiner-system threshold conjecture. The threshold for the appearance of an (n,k,k−1)(n,k,k-1)-Steiner system in Hk(n;p)\mathcal{H}_k(n;p) is

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

The lower bound comes from the requirement that no facet, meaning a (k−1)(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.

References

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.