# Properties of Some Random Graphs

Working in a problem the following family of graphs appears naturally. Consider the set $A_{n}=\{1,2,3,\ldots,n\}$ and let $\mathcal{C_{n}}$ be the set of all permutations of $A_{n}$ of order $n$ (cycles of order $n$). Let $\sigma_{1},\sigma_{2},\ldots,\sigma_{d}$ be random elements chosen uniformly and without repetition from $\mathcal{C}_{n}$.

Now we construct the random graph $\mathcal{G}$ where the node set is $A_{n}$ and there is an edge between each node $i$ and $\sigma_{p}(i)$ for every $p\in\{1,2,\ldots,d\}$. It's clear that every node in the graph $\mathcal{G}$ has degree at most $2d$ (we ignore multiple edges and loops).

My questions are:

• Did anybody studied these graphs before?
• Is it known what is the asymptotic diameter of $\mathcal{G}$ for fixed $d$ as $n$ increases with high probability?
• Estimates on the Cheeger constant? Laplacian?

Yes, this model has been studied. You should look at Chapter 9 of Janson, Luczak and Rucinski's Random Graphs book, and in particular at Corollary 9.44. This corollary is in fact a rather well-known theorem, which I'll now explain.

Let $H_n(d)$ be the distribution you describe (Edit: more accurately, $H_n(d)$ is the distribution of the union of $d$ independent and uniformly random cycles, conditioned on the result being a simple graph), and let $G_n(2d)$ be the distribution of a uniformly random $2d$-regular (all nodes having degree exactly $2d$) simple graph. Then Corollary 9.44 states that for any fixed $d$, $H_n(d)$ and $G_n(2d)$ are contiguous, which means that for any graph property $A$,

$$\mathbb{P}(H_n(d) \in A) \to 1~\mbox{as}~n\to\infty$$ if and only if $$\mathbb{P}(G_n(2d) \in A) \to 1~\mbox{as}~n\to\infty.$$

In other words, if you are only interested in studying whether things hold asymptotically almost surely, these two models are equivalent.

In particular, its isoperimetric constant is $(1/2+o(1)) d$, its diameter is $(1+o(1)) \log_{d-1} (n)$, and all eigenvalues except for the largest are $\sqrt{2(d-1)}+o(1)$.

• I don't have the book in front of me, but doesn't the usual description of $H_n(d)$ come from uniformly chosen permutations rather than uniformly chosen cycles? Apr 2, 2011 at 19:13
• No, it's normally cycles. The H stands for Hamiltonian. It's actually a conjecture in the book that you can use permutations instead of cycles (except when $d=1$), and I'm pretty sure that conjecture has been proved correct, but I don't remember a reference. Apr 2, 2011 at 19:21
• My bracketed comment should have said (except for $d=1$, when you in fact must use permutations instead of cycles). Apr 2, 2011 at 19:41
• There is a slight inaccuracy here. I don't have the book with me, and certainly there is a very similar theorem in there. However, the union of $d$ independent cycles will contain a (roughly) Poisson number of double edges. As I recall, the correct formulation may be that $H_n(d)$ and $G'_n(2d)$ are contiguous, where $G'$ is a $2d$-regular uniform multi-graph. Also, the $2d$-regular graph is contiguous with $H_n(d)$ conditioned to be simple, an event with probability tending to some constant $c_d$ (from the Poisson law for double edges). This does not affect the applications in any way.
– Omer
Apr 4, 2011 at 0:14
• Omer, yes, that's right, you need to condition $H_n(d)$ to be simple or else the result is incorrect. I'll expand my answer. Apr 4, 2011 at 20:07

For those interested in further reading about the contiguity of the above mentioned models for random regular graphs and generalization of the above: Catherine Greenhill, Svante Janson, Jeong Han Kim and Nicholas C. Wormald, Permutation pseudographs and contiguity, Combinatorics, Probability and Computing 11 (2002), 273 - 298.