Normality conjecture for cycle and matching counts in random regular graphs

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,nd}\min\{d,n-d\}\to\infty

as nn\to\infty. The number of \ell-cycles in G(n,d){\mathcal G}(n,d) is asymptotically normal for all 3n3\le \ell\le n, and the number of \ell-matchings in G(n,d){\mathcal G}(n,d) is asymptotically normal for all 3n/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.

Sources & referencesView supporting material

Primary source

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.