The threshold conjecture for star decompositions of random regular graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.