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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: