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

166 Views Asked by At

$\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

There are 1 best solutions below

0
On BEST 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.