2
$\begingroup$

On pg 5 of Janson's paper Random Regular Graphs: Asymptotic Distributions and Contiguity the following is mentioned:

Given $r$ and a vertex set $V$ with $n$ elements (with $rn$ even), define a configuration to be a perfect matching of the $rn$ elements of $V\times \{1, \ldots, r\}$. Every configuration projects to an $r$-regular multigraph on $V$. It is easily seen that if we condition on there being no loops or multiple edges, we obtain a random $r$-regular graph $G(n, r)$ with the usual uniform distributions.

If I understand correctly, the last line says that:

Let $G$ and $H$ be two $r$-regular graphs on $V$ (no multiple edges or loops), then the number of configurations on $V\times \{1, \ldots, r\}$ whihc project to $G$ same as the number of configuration which project to $H$.

I am unable to prove this. I was able to prove this when $r=2$, because any $2$-regular graph is a union of $2$-cycles. So I was able to explicitly compute the number of configurations of $V\times \{1, 2\}$ which project to a given $2$-regular graph $G$.

Can somebody help me see this for a general $r$? Thank you.

$\endgroup$
2
$\begingroup$

The only way to change the configuration without changing the graph is to permute the elements $(v,1), (v,2), \dots, (v,r)$ for each of the vertices $v \in V$. If the graph has no multiple edges or loops, then all $(r!)^n$ permutations give different configurations, so there are $(r!)^n$ configurations that give any graph $G$.

To check this, we check that no nontrivial permutation of a configuration can leave it unchanged. Each edge of the configuration goes from $(v,i)$ to $(w,j)$ with $v \ne w$; there is no other edge $(v,i')$ to $(w,j')$, so if we want to make sure there is still an edge from $(v,i)$ to $(w,j)$, we had better leave $(v,i)$ and $(w,j)$ unchanged by the permutation. Since this is true for all edges, and since all elements of the configuration are endpoints of such an edge, the permutation must be the identity.

(But if we had two multiple edges, there is a nontrivial permutation swapping them, and we had a loop, which is an edge from $(v,i)$ to $(v,j)$, there is a nontrivial permutation swapping the endpoints. So both conditions are necessary.)

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