Sandbox:DavidKohler/Alon try 1/Probabilistic models for regular graphs

In order to obtain a probability space of random d-regular graphs we use the fairly standard model which generates regular graphs using permutations.

Definition

We can produce a d-regular graph on n vertices, assuming d is even, as follows. Chose d/2 permutations of n elements that we'll denote by π₁, π₂, ..., π_d/2. We construct a graph whose vertices are the integers from 1 to n and where the couple (i, j ) is an edge if j = π_k(i ) or j = π^-1_k(i ) for some k between 1 and d/2. We allow for multiple edges and self-loops which makes then the graph d-regular (we chose to think of this graph as being undirected). Chose the d/2 permutations uniformly and independently among all n ! permutations to obtain a probability space that we will denote by G_n,d and called the standard model for random d-regular graphs.

Example

Let's construct a 4-regular graph, G, on 6 vertices. For this we need to choose (uniformly and independently) 2 permutations σ and τ of 6 elements. Say we have:

$\sigma =\left({\begin{array}{cccccc}1&2&3&4&5&6\\2&6&5&4&1&3\end{array}}\right)\quad \tau =\left({\begin{array}{cccccc}1&2&3&4&5&6\\5&2&3&6&4&1\end{array}}\right)$

Then we can see for example that since σ(1)=2 that we have an edge connecting the vertex 1 to the vertex 2. And since σ^-1(1)=5 we also have an edge connecting the vertex 1 to the vertex 5. The adjacency matrix of the graph that we obtain is thus:

$A_{G}=\left({\begin{array}{cccccc}0&1&0&0&2&1\\1&2&0&0&0&1\\0&0&2&0&1&1\\0&0&0&2&1&1\\2&0&1&1&0&0\\1&1&1&1&0&0\end{array}}\right)$

and a visual representation of this 4-regular graph is: