MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question
up vote 15 down vote accepted

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

share|cite|improve this answer
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? – Matthew Kahle Apr 2 '11 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. – Louigi Addario-Berry Apr 2 '11 at 19:21
Thanks Louigi --- that's interesting. – Matthew Kahle Apr 2 '11 at 19:32
My bracketed comment should have said (except for $d=1$, when you in fact must use permutations instead of cycles). – Louigi Addario-Berry Apr 2 '11 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 '11 at 0:14

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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