2
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.