The threshold conjecture for star decompositions of random regular graphs
Let be fixed, and let denote the largest positive integer such that, asymptotically almost surely, the random -regular graph contains an independent set of size . For fixed positive integers with , star-decomposition threshold conjecture.
The independent-set condition is necessary because, when , the leaves in a -star decomposition form an independent set of size . The conjecture asserts that this necessary condition determines the asymptotic threshold for -star decompositions of random regular graphs; the supplied text does not state that it has been proved or disproved.
References
- Michelle Delcourt, Catherine Greenhill, Mikhail Isaev, Bernard Lidický and Luke Postle, “Decomposing random regular graphs into stars”, arXiv:2308.16037 (2025).
Progress summary
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.