Decomposing random regular graphs into stars
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\).
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Almost all 5-regular graphs have a 3-flow
- Almost all cubic graphs are Hamiltonian
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Decomposition of complete multigraphs into stars
- Decompositions of complete multigraphs into stars of varying sizes
- Differential equations for random processes and random graphs
- From the theory of regular graphs of third and fourth degree
- scientific article; zbMATH DE number 3710196 (Why is no real title available?)
- scientific article; zbMATH DE number 729555 (Why is no real title available?)
- scientific article; zbMATH DE number 1460605 (Why is no real title available?)
- Improved replica bounds for the independence ratio of random regular graphs
- Large independent sets in random regular graphs
- Maximum independent sets on random regular graphs
- Modular orientations of random and quasi-random regular graphs
- Nowhere-zero 3-flows and modulo \(k\)-orientations
- On claw-decomposition of complete graphs and complete bigraphs
- On the independence and chromatic numbers of random regular graphs
- On the number of perfect matchings in random lifts
- Random 4-regular graphs have 3-star decompositions asymptotically almost surely
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Replica bounds by combinatorial interpolation for diluted spin systems
- The asymptotic connectivity of labelled regular graphs
- The asymptotic number of labeled graphs with given degree sequences
- The isoperimetric number of random regular graphs
- The real truth about star designs
- The weak 3-flow conjecture and the weak circular flow conjecture
This page was built for publication: Decomposing random regular graphs into stars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930157)
