14
$\begingroup$

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

2 Answers 2

17
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Apr 2, 2011 at 19:13
  • $\begingroup$ 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. $\endgroup$ Apr 2, 2011 at 19:21
  • $\begingroup$ My bracketed comment should have said (except for $d=1$, when you in fact must use permutations instead of cycles). $\endgroup$ Apr 2, 2011 at 19:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – Omer
    Apr 4, 2011 at 0:14
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2011 at 20:07
4
$\begingroup$

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.

Link: http://web.maths.unsw.edu.au/~csg/papers/gjkw-revised.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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