The threshold conjecture for star decompositions of random regular graphs

At least 2 years old · documented by

Let d≥3d\geq 3 be fixed, and let \kindactuald\kindactual{d} denote the largest positive integer kk such that, asymptotically almost surely, the random dd-regular graph Gn,d\mathcal{G}_{n,d} contains an independent set of size (2k−d)n2k\frac{(2k-d)n}{2k}. For fixed positive integers d,kd,k with d≥3d\geq 3, star-decomposition threshold conjecture.

Pr(Gn,d has a k-star decomposition)→{1 if k≤\kindactuald,0 if k>\kindactuald.\mathop{\mathrm{Pr}}\big(\mathcal{G}_{n,d} \text{ has a $k$-star decomposition}\big)\rightarrow \begin{cases} 1 & \text{ if $k \leq \kindactual{d}$,}\\ 0 & \text{ if $k > \kindactual{d}$.} \end{cases}

The independent-set condition is necessary because, when k>d/2k>d/2, the leaves in a kk-star decomposition form an independent set of size (2k−d)n2k\frac{(2k-d)n}{2k}. The conjecture asserts that this necessary condition determines the asymptotic threshold for kk-star decompositions of random regular graphs; the supplied text does not state that it has been proved or disproved.

References

Primary source

Michelle Delcourt, Catherine Greenhill, Mikhail Isaev, Bernard Lidický and Luke Postle, “Decomposing random regular graphs into stars”, arXiv:2308.16037 (2025).

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.