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

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?

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?