The fractional-decomposition hitting-time conjecture for random hypergraph processes

From papers

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 (k1)(k-1)-subset of vertices; it is uncovered until it belongs to an exposed edge. A fractional KkK_k-decomposition assigns weights in [0,1][0,1] to the exposed kk-edges so that every facet has total incident weight 11. Fractional-decomposition hitting-time conjecture. As nn\to\infty with kk fixed, asymptotically almost surely the hitting time for the disappearance of uncovered facets equals the hitting time for the appearance of a fractional KkK_k-decomposition. This would show that uncovered facets are the only hitting-time obstruction to fractional decompositions, paralleling the known fractional-matching phenomenon; it remains open for these decompositions.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.