# A random $r$-regular graph can be generated by taking union of a a random $(r-1)$-regular graph and a perfect matching.

$$\newcommand{\lrp}[1]{\left(#1\right)}$$ $$\newcommand{\set}[1]{\{#1\}}$$ $$\newcommand{\mc}{\mathcal}$$ $$\newcommand{\E}{\mathbb E}$$ $$\newcommand{\N}{\mathbb N}$$

Definition. Let $$(\Omega_n, \mc F_n)$$ be a sequence of measurable spaces and suppose we are given two probability distributions $$P_n$$ and $$Q_n$$ on $$(\Omega_n, \mc F_n)$$ for each $$n$$. We say that the sequences $$(P_n)$$ and $$(Q_n)$$ are contiguous if for each sequence of events $$(A_n)$$, where $$A_n\in \mc F_n$$, we have that $$P_n(A_n)\to 1$$ as $$n\to \infty$$ if and only if $$Q_n(A_n)\to 1$$ as $$n\to \infty$$.

We $$\mc G^*(n, r)$$ to denote the set of all the $$r$$-regular multigraphs on the set $$V=[n]=\set{1 , \ldots, n}$$ (a multigraphs allows for loops and multiple edges). We define a probability distribution on $$\mc G^*(n, r)$$ as follows.

Assume $$rn$$ is even. Define a configuration as a perfect matching of the set $$V\times [r]$$, where $$[r]=\set{1 , \ldots, r}$$. Given a configuration, we naturally obtain an $$r$$-regular multigraph on $$V$$ by projecting" the configuration. The uniform probability distribution on the set of configurations pushes forward to give a probability distribution $$G^*(n, r)$$ on $$\mc G^*(n, r)$$.

Note that if $$\sigma$$ and $$\tau$$ are two probability distributions on $$\mc G^*(n, r)$$ and $$\mc G^*(n, s)$$ respectively, then we get a probability distribution $$\sigma+\tau$$ on $$\mc G^*(n, r + s)$$ as follows. Put the product measure $$\sigma\otimes \tau$$ on $$\mc G^*(n, r)\times \mc G^*(n, r)$$ and define $$\sigma+\tau$$ as the push-forward of $$\sigma\otimes \tau$$ under the union map" $$\mc G^*(n, r)\times \mc G^*(n, s) \to \mc G^*(n, r+s)$$.

The following is true and I want to understand the proof of this.

Theorem of Interest $$G^*(n, r-1) + G^*(n, 1)$$ is contiguous with $$G^*(n, r)$$.

In Janson's paper Random Regular Graphs: Asymptotic Distributions and Contiguity [J] the author hints (on pg. 16) that the above theorem is a consequence of the following two.

Theorem. [J, Theorem 4] Let $$M_n^*:\mc G^*(n, r)\to \N_0$$ be the random variable which counts the number of perfect matchings of a given $$r$$-regular multigraph. Then if $$r\geq 3$$, and $$n$$ is even, we have $$\frac{M_n^*}{\E[M_n^*]} \xrightarrow{d} \prod_{i=0}^\infty \lrp{1+ \frac{(-1)^i}{(r-1)^i}}^{Z_i} e^{(-1)^{i-1}/2i}$$ where $$Z_i\sim \text{Po}\lrp{ \frac{(r-1)^i}{2i}}$$ are independent Poisson random variables. Also $$\E[M_n^*] \sim \sqrt{2} \lrp{ \frac{(r-1)^{(r-1)/2}}{r^{(r-2)/2}}}^n$$ and $$\E[(M_n^*)^2]/(\E[M_n^*])^2 \to \sqrt{ \frac{r-1}{r-2}}$$

Let $$P_n$$ and $$Q_n$$ be probability distribution on $$(\Omega_n, \mc F_n)$$. Then $$Q_n=Q_n^a+ Q_n^s$$, where $$Q_n^a$$ is absolutely continuous with respect to $$P_n$$ and $$Q_n^s$$ is singular with respect to to $$P_n$$. We write $$dQ_n/dP_n$$ to denote the Radon-Nikodym derivative of $$Q_n^a$$ with respect to $$P_n$$.

Theorem. [J, Proposition 3] Suppose $$L_n=dQ_n/dP_n$$, regarded as a random variable on $$(\Omega_n, \mc F_n, P_n)$$, converges in distribution to some random variable $$L$$ as $$n\to \infty$$. Then $$(P_n)$$ and $$(Q_n)$$ are contiguous if and only if $$L>0$$ a.s. and $$\E[L]=1$$.

I am not able to see how the above two theorems prove the theorem of interest.

## 1 Answer

We just do the same thing as Janson does for the Hamiltonian cycles. (I am just doing my best to do this below; in particular, I probably won't be able to answer any questions regarding the fine points of measure theory as they apply here.)

Let $$P_n$$ be the distribution of the random multigraph $$G^*(n,r)$$, and define $$Q_n$$ by $$\frac{dQ_n}{dP_n} = \frac{M_n^*}{\mathbb E[M_n^*]}$$. Janson's theorem $$4$$ tells us that $$L_n = \frac{dQ_n}{dP_n}$$ converges to a random variable $$L$$ as $$n\to \infty$$, given by the formula with the infinite product.

Go back to Janson's Theorem 1 to see when the conditions "$$L>0$$ a.s. and $$\mathbb E[L]=1$$" are satisfied. We always have $$\mathbb E[L]=1$$; we have $$L>0$$ a.s. when we have $$\frac{(-1)^i}{(r-1)^i} > -1$$ for all $$i$$, which tells us that we must have $$r>2$$. So Proposition 3 tells us that $$P_n$$ and $$Q_n$$ are contiguous, and all that's left is to figure out what the heck $$Q_n$$ is.

Just as Janson does for Hamiltonian cycles, we can give $$Q_n$$ an interpretation here, as follows:

Let $$\overline{\Omega}_n$$ be the set of all pairs $$(\tilde{G}, \tilde{M})$$, where $$\tilde{G}$$ is an $$[n] \times [r]$$ configuration, and $$\tilde{M}$$ is a set of edges in $$\tilde{G}$$ that projects to a perfect matching. Pick $$(\tilde{G}, \tilde{M})$$ uniformly at random from $$\overline{\Omega}_n$$ and let $$G^*$$ be the projection of $$G$$.

We claim that $$Q_n$$ is the distribution of $$G^*$$, because

• The probability of getting a particular $$G^*$$ is proportional to the number of pairs $$(\tilde{G}, \tilde{M})$$ where $$\tilde G$$ projects to $$G^*$$, which is the number of ways to pick out some edges of $$\tilde{G}$$ that project to a matching: the number of matchings in $$G^*$$.
• Defining $$\frac{dQ_n}{dP_n} = \frac{M_n^*}{\mathbb E[M_n^*]}$$ means that the $$Q_n$$-probability of an event $$A$$ is $$\frac{\mathbb E[M_n^* 1_A]}{\mathbb E[M_n^*]}$$. When $$A$$ is the event "we picked $$G^*$$", the expectation $$\mathbb E[M_n^* 1_A]$$ simplifies to the number of perfect matchings in $$G^*$$, so the $$Q_n$$ probability of picking $$G^*$$ is also proportional to how many perfect matchings it has.

We can partition $$(\tilde{G}, \tilde{M})$$ into equivalence classes by the set of elements of $$[n]\times[r]$$ saturated by $$\tilde{M}$$. By symmetry, the distribution of the projection $$G^*$$ obtained when we restrict to any single equivalence class is the same. In particular, we can pick out the equivalence class $$\overline{\Omega}_n'$$ where $$\tilde{M}$$ saturates the vertices $$[n] \times \{r\}$$.

Within this $$\overline{\Omega}_n'$$, the distribution of $$G^*$$ is exactly the distribution of $$G^*(n,r-1)$$ plus a perfect matching. So $$Q_n$$ has the $$G^*(n,r-1) + G^*(n,1)$$ distribution, and the contiguity result we proved is the same as the contiguity result we wanted.