For every fixed varepsilon>0, determine whether the random graph G(n,p) has, with high probability, a fractional triangle decomposition precisely at the conjectured threshold p=(1+o(1))√frac3log n2n; in particular, the conjecture asserts that p≥ (1+varepsilon)√frac3log n2n suffices for a fractional K_3-decomposition with high probability, while p≤ (1-varepsilon)√frac3log n2n does not.

Fractional clique decomposition threshold conjecture

For every fixed $\varepsilon>0$ , determine whether the random graph $G(n,p)$ has, with high probability, a fractional triangle decomposition precisely at the conjectured threshold $p=(1+o(1))\sqrt{\frac{3\log n}{2n}}$ ; in particular, the conjecture asserts that $p\ge (1+\varepsilon)\sqrt{\frac{3\log n}{2n}}$ suffices for a fractional $K_3$ -decomposition with high probability, while $p\le (1-\varepsilon)\sqrt{\frac{3\log n}{2n}}$ does not.

References

Primary source

arXiv

Additional references

The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling — arXiv — Tuan Tran

extremal-combinatorics hypergraph-theory probabilistic-combinatorics

Posted 5 days ago · edited 5 days ago

Progress summary

Refreshed 5 days ago

Claimed progress

A new probabilistic result reaches the correct power-law scale, but the conjectured exact threshold remains open.

Yuster posed the problem in 2007: determine the sharp random-sparsification threshold for fractional triangle decompositions. Mahabaduge and Simkin conjectured the logarithmic threshold in random graphs, while the newer framework also treats uniform hypergraphs.

Known results

Mahabaduge and Simkin previously obtained the graph bound $p\ge n^{-4/11+o(1)}$ .
For every fixed $\varepsilon>0$ , the conjectured graph threshold is $p\geq (1+\varepsilon)\sqrt{\frac{3\log n}{2n}}$ .

2026 preprint: correct polynomial order

Tuan Tran claims that, for $k\ge 2$ and $r\ge k+1$ , $G^{(k)}(n,p)$ has a fractional $K_r^{(k)}$ -decomposition with high probability when $p\ge n^{-\frac{r-k}{\binom{r}{k}-1}+\varepsilon}$ . For triangles this gives $p\ge n^{-1/2+o(1)}$ , closing the previous polynomial gap, but it does not prove the conjectured logarithmic threshold or an exact constant.

Current status (as of October 2026): The correct polynomial-order threshold is claimed for random graphs and uniform hypergraphs, but the sharp logarithmic threshold conjecture remains open.

Sources

No solutions have been posted yet.