3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.