Random-graph tree-cover threshold conjecture

Let $G(n,p)$ be the binomial random graph, and let $\mathrm{tp}_r(G(n,p))$ be the minimum number of monochromatic trees needed to partition the vertex set in every $r$-edge-coloring. Here, “a.a.s.” means with probability tending to one as $n\to\infty$.

Random-graph tree-cover threshold conjecture. For every $\epsilon>0$ and every $r\geq 1$, if

$$p\geq \left(\frac{(1+\epsilon)r\log n}{n}\right)^{1/r},$$

then a.a.s.

$$\mathrm{tp}_r(G(n,p))\leq r.$$

This conjecture aims to identify the sharp threshold for monochromatic tree partitions in random graphs. The $r=2$ case was proved by Kohayakawa, Mota, and Schacht while the general case remains open.