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?
> 
> 
> 



Properties of Some Random Graphs
Yes, this model has been studied. You should look at Chapter 9 of Janson, Luczak and Rucinski's [Random Graphs book](http://rads.stackoverflow.com/amzn/click/0471175412), 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](ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf) is $(1/2+o(1)) d$, its [diameter](http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf) is $(1+o(1)) \log\_{d-1} (n)$, and [all eigenvalues except for the largest](http://www.math.ubc.ca/~jf/pubs/web_stuff/alon.html) are $\sqrt{2(d-1)}+o(1)$. 


