The threshold conjecture for star decompositions of random regular graphs

Let d3d\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 (2kd)n2k\frac{(2k-d)n}{2k}. For fixed positive integers d,kd,k with d3d\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 (2kd)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.

Sources & referencesView supporting material

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.