← All problems

Normality conjecture for cycle and matching counts in random regular graphs

5 years old · traced to

Let G(n,d){\mathcal G}(n,d) be the uniform random dd-regular graph on nn vertices. For an integer ℓ\ell, an ℓ\ell-cycle is a cycle with ℓ\ell vertices, and an ℓ\ell-matching is a matching with ℓ\ell edges.

Normality conjecture. Suppose

min⁡{d,n−d}→∞\min\{d,n-d\}\to\infty

as n→∞n\to\infty. The number of ℓ\ell-cycles in G(n,d){\mathcal G}(n,d) is asymptotically normal for all 3≤ℓ≤n3\le \ell\le n, and the number of ℓ\ell-matchings in G(n,d){\mathcal G}(n,d) is asymptotically normal for all 3≤ℓ≤n/23\le \ell\le n/2.

This conjecture asserts that normal limiting behavior persists across the full ranges of cycle and matching sizes, extending the paper's discussion of possible distributional phase transitions for these counts.

References
  1. Pu Gao, “The number of perfect matchings, and the nesting properties, of random regular graphs”, arXiv:2104.11850 (2022).

Progress summary

Never refreshed

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.