The number of perfect matchings, and the nesting properties, of random regular graphs

Abstract

We prove that the number of perfect matchings in $\mathcal{G}(n,d)$ is asymptotically normal when $n$ is even, $d\to \infty$ as $n\to \infty$, and $d=O(n^{1/7}/{\log }^{2}n)$. This is the first distributional result of spanning subgraphs of $\mathcal{G}(n,d)$ when $d\to \infty$. Moreover, we prove that $\mathcal{G}(n,d-1)$ and $\mathcal{G}(n,d)$ can be coupled so that $\mathcal{G}(n,d-1)$ is a subgraph of $\mathcal{G}(n,d)$ with high probability when $d\to \infty$ and $d=o(n^{1/3})$. Further, if $d=\Omega ({\log }^{7}n)$, $d=O(n^{1/7}/{\log }^{2}n)$, and $d\le d^{\prime }\le n-1$ then $\mathcal{G}(n,d)$ and $\mathcal{G}(n,d^{\prime })$ can be coupled so that asymptotically almost surely $\mathcal{G}(n,d)$ is a subgraph of $\mathcal{G}(n,d^{\prime })$.