2025/03/12 by Harangi, Viktor · 2 citations
#05C69 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2503.09458
A k-star decomposition of a graph is a partition of its edges into k-stars (i.e., k edges with a common vertex). The paper studies the following problem: for what values of k>d/2 does the random d-regular graph have a k-star decomposition (asymptotically almost surely, provided that the number of edges is divisible by k)? Delcourt, Greenhill, Isaev, Lidický, and Postle proposed the following conjecture. It is easy to see that a k-star decomposition necessitates the existence of an independent set of density 1-d/(2k). So let kindd be the largest k for which the random d-regular graph a.a.s. contains an independent set of this density. Clearly, k-star decompositions cannot exist for k>kindd. The conjecture suggests that this is essentially the only restriction: there is a threshold k^⋆d such that k-star decompositions exist if and only if k ≤ k^⋆d, and it (basically) coincides with the other threshold, i.e., k^⋆d ≈ kindd. We confirm this conjecture for sufficiently large d by showing that a k-star decomposition exists if d/2< k < kindd. In fact, we prove the existence even if k=kindd for degrees d with asymptotic density 1.