Decomposing random regular graphs into stars (Q6930157)

Can you partition the edge set of a random \(d\)-regular graph with \(n\) vertices (\(\mathcal{G}_{n,d}\)) into disjoint \(k\)-stars? This article conjectures there is a threshold value \(k^\ast (d)\) such that this is possible with high probability (w.h.p.) as \(n\) grows large for \(k\leq k^\ast (d)\), and impossible w.h.p.\ for \(k> k^\ast (d)\). More precisely, there are some partial answers: the non-existence of a \(k\)-star decomposition in \(\mathcal{G}_{n,d}\) w.h.p.\ is proven for \(k>k^+(d)\) using a first moment method, where \(k^+(d)\) is defined as the threshold value for which the expected number of independent sets of size \((2k-d)n / (2k)\) in \(\mathcal{G}_{n,d}\) goes to \(0\). This value is believed to be almost sharp since the conjecture is in fact \(k^\ast (d)\in \{k^+(d)-1,k^+(d)\}\).\N\NThe authors also prove existence w.h.p.\ for some values of \(k\leq d/2\) using, in particular, a connection between \(k\)-star decompositions and \(\beta\)-orientations. Finally, existence w.h.p.\ is proven for all \(d/2<k\leq k^-(d)\), for some computable boundary value \(k^-(d)\) using the small subgraph conditioning method. Numerically, it is found that \(k^-(d)\) is sufficiently close (often equal) to \(k^+(d)\) that the conjecture could be verified for any \(d\leq 200\) and \(d/2\leq k\).