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

2 Answers 2

Reset to default
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)$.

Improve this answer
$\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$
    – Matthew Kahle
    Commented 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$
    – Louigi Addario-Berry
    Commented 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$
    – Louigi Addario-Berry
    Commented 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
    Commented 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$
    – Louigi Addario-Berry
    Commented 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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .