Visualizing the Configuration model |

A way to generate a random $k$ -regular graph is via the configuration model. Here is a short description of the model. Imagine that each vertex has k tokens. This suggests that we have in total kn tokens, where $n$ is the number of vertices and you can freely think of $n \rightarrow +\infty$ . Also, let me mention that in whatever follows, $k$ is a constant. Then we pair up tokens randomly. Of course we will assume that when $k$ is odd, that $n$ is even, otherwise the pairing is impossible. Then, we project the configuration in a multigraph in the obvious way, which I describe by an example: if the pair between token $j$ of vertex $v_x$ pairs with the token $l$ of vertex $v_y$ then we add an edge between $v_x,v_y$ . A nice way to visualize the configuration model is via the following picture where the tokens are coordinates on the x-axis [bucketed according to which vertex they belong to] and the pairings are shown via the semicircles:

If anyone wants the MATLAB script before I clean it up just let me know. How many such configurations exist? Let’s call their number $F(k,n)$ to denote that it is a function of $k$ and $n$ . Well, consider the last token on the x-axis, i.e., the token $kn$ . It will have to pair with one token. How many choices does it have? Clearly, $kn-1$ . Therefore We obtain the obvious recurrence $F(k,n) = (kn-1) F(k,n-2)$ where $F(k,2)=1$ . The solution to this recurrence has a name, since it is an important recurrence. The name is double factorial. Namely, $F(k,n) = (kn-1)!! = \frac{(kn)!}{2^{(kn)/2}(kn/2)!}$ . In a follow up post, I will write more on different existing methods to generate $k$ -regular graphs. For now, remember that this technique is good for generating regular graphs when $k$ is small, since as $k$ increases, the probability of the graph being simple decreases exponentially, and that will force us to execute the pairing exponential number of times.