The hitting-time conjecture for Steiner systems in random hypergraph processes

About 9 years old · traced to

Let KknK_k^n be the complete kk-uniform hypergraph on nn vertices, and expose its edges one by one in a uniformly random order to obtain the random hypergraph process. A facet is a (k−1)(k-1)-subset of vertices, and a facet is covered when it is contained in at least one exposed edge. Steiner-system hitting-time conjecture. As n→∞n\to\infty with kk fixed, asymptotically almost surely a Steiner system appears at the very moment that all facets are covered. This would identify the sole obstruction to a Steiner system in the process with the presence of uncovered facets, extending the corresponding graph-process phenomenon; the analogous assertion for perfect matchings in hypergraphs is noted as open.

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.