The threshold conjecture for fractional decompositions of 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 a fractional KkK_k-decomposition of a kk-uniform hypergraph HH be a weight function w:H[0,1]w:H\to[0,1] such that, for every facet fKk1(H)f\in K_{k-1}(H),

feHw(e)=1.\sum_{f\subseteq e\in H}w(e)=1.

Fractional-decomposition threshold conjecture. The threshold for the appearance of fractional KkK_k-decompositions in Hk(n;p)\mathcal{H}_k(n;p) is

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

The threshold is bounded below by the disappearance of uncovered facets and above by the threshold for Steiner systems. The conjecture is motivated by the known hitting-time result for fractional matchings, while the corresponding threshold and hitting-time statements for these fractional decompositions remain open.

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.