In how many ways can we generate a given bipartite multigraph via the bipartite configuration model? - MathOverflow

In how many ways can we generate a given bipartite multigraph via the bipartite configuration model?

2012-04-24T10:54:36Z

Suppose I have two multisets, $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. We can construct a (random) bipartite multigraph with the vertex bipartition $\text{set}(A) \cup \text{set}(B)$ by the following process:

start with the null graph on vertex multiset $A \cup B$,
pick a (random) permutation $\alpha$ of $\{1,2,\ldots,n\}$,
draw edges from $a_i$ to $b_{\alpha(i)}$ for all $i \in \{1,2,\ldots,n\}$,
identify vertices $a_i$ and $a_j$ whenever $a_i=a_j$, and similarly, identify vertices $b_i$ and $b_j$ whenever $b_i=b_j$.

This could be described as a version of the configuration model for bipartite graphs (although, usually the configuration model restarts if parallel edges occur, and I don't want to do that).

For example, if $A=\{1,2,2,2,3\}$ and $B=\{4,4,5,5,5\}$, and $\alpha=\text{id}$ then we generate the multigraph with bipartition $\{1,2,3\} \cup \{4,5\}$ and edge multiset $\{14,24,25,25,35\}$. We could also have generated the same multigraph with $\alpha=(12)$, and $\alpha=(23)$ and a variety of other ways.

Question: Given a bipartite multigraph, in how many ways could it have been generated by the above process?

A related problem, the enumeration of contingency tables, is #P-complete (this gives the number of distinct bipartite graphs that could have arisen). See: M. Dyer, R. Kannan, J. Mount, Sampling Contingency Tables, Random Structures & Algorithms 10 (1997), 487–506.

Presumably, the problem I mention above is "hard" (although, feel free to prove me wrong!), which suggests an algorithmic approach is required to answer the question in general.

This leads me to the sub-questions:

Sub-question: Is there an efficient way to compute these numbers (other than some kind of backtracking algorithm)?

and

Sub-question: Does there exist a graph whose automorphisms correspond (naturally) to the different ways of generating a given bipartite multigraph by the above method?

If it is possible to do the above, then we could use e.g. nauty to compute it easily.

(Note: This question is "the other side of the coin" of a math.SE question: What is the number of bijections between two multisets? However, I tried to make this question self-contained.)

Answer by Zur Luria for In how many ways can we generate a given bipartite multigraph via the bipartite configuration model?

2012-04-24T12:07:54Z

Hi, I'm going to try to answer your first question, which is: Given a bipartite multigraph on $set(A)\cup set(B)$, in how many ways could it have resulted from the described procedure?

I think that your question is related to Barvinok's work on contingency tables. In particular, take a look at theorem 1.2 here:

http://www.math.lsa.umich.edu/~barvinok/newtab.pdf

Let's say that $set(A)$ has $k$ elements and $set(B)$ has $m$ elements, and let $M$ be the adjacency matrix of the resulting bipartite multigraph. That is, $m_{ij}$ is the number of edges between the $i$'th element of $set(A)$ and the $j$'th element of $set(B)$. Furthermore, let $r_1, ... ,r_k$ be the degrees of the vertices in $set(A)$ and let $s_1, ... ,s_m$ be the corresponding degrees for $set(B)$.

Consider the following $n \times n$ block matrix $X$: There are $k \times m$ blocks, and the size of the $i,j$-th block is $r_i$ by $s_j$. Each row of $X$ corresponds to an element of $A$, and each column of $X$ corresponds to an element of $B$, and so the perfect matching $\alpha$ is a permutation matrix. This permutation matrix corresponds to the original graph iff there are $m_{ij}$ ones in the $i,j$-th block of $X$.

Thus, your question is equivalent to: How many order $n$ permutation matrices are there with $m_{ij}$ ones in the $i,j$-th block of $X$? You have to choose $m_{i,j}$ rows of $r_i$ for the $i,j$-th block for every $j$, and do the same for the columns. Then, once you know which rows and columns correspond to which blocks, you have to choose a permutation matrix of order $m_{i,j}$ for each block, so the answer is:

$$ \prod_i{\binom{r_i}{m_{i,1}, ... ,m_{i,m}}} \prod_j{\binom{s_j}{m_{1,j}, ... ,m_{k,j}}} \prod_{i,j}{m_{i,j}!} = $$ $$ \frac{\prod_i{r_i!} \prod_j{s_j!} }{\prod_{i,j}{m_{i,j}!}} .$$

This counting argument is very well presented in Barvinok's paper.

Answer by Brendan McKay for In how many ways can we generate a given bipartite multigraph via the bipartite configuration model?

2012-04-24T13:03:44Z

Zur's answer is correct. My explanation (using Zur's notation): Think of the configuration (which I am always nagging people to call a pairing since "configuration" is way overworked) as a matching in $K_{n,n}$ where $n=\sum s_i = \sum t_j$. To get all the pairings that give a particular multigraph you can arbitrarily permute the ends of the matching edges within each degree class on each side. That gives $\prod s_i!\prod t_j!$ possibilities. Many of them give the same multigraph, but you can get all such by permuting one end of the edges belonging to each multiedge, giving a factor of $\prod m_{ij}!$ to divide by. This counting goes back to the 1970s at least (eg. Bender's papers).