The threshold conjecture for Steiner systems in random hypergraphs
The threshold conjecture for Steiner systems in random hypergraphs
Let be the complete -uniform hypergraph on vertices, let be the random -uniform hypergraph obtained by retaining each edge independently with probability , and let an -Steiner system be a collection of -edges in which every -subset is contained in exactly one edge. Steiner-system threshold conjecture. The threshold for the appearance of an -Steiner system in is
The lower bound comes from the requirement that no facet, meaning a -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.