In how many ways can we generate a given bipartite multigraph via the bipartite configuration model? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:42:25Z http://mathoverflow.net/feeds/question/95011 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95011/in-how-many-ways-can-we-generate-a-given-bipartite-multigraph-via-the-bipartite-c In how many ways can we generate a given bipartite multigraph via the bipartite configuration model? Douglas S. Stones 2012-04-24T10:54:36Z 2012-04-24T13:03:44Z <p>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:</p> <ul> <li>start with the null graph on vertex multiset $A \cup B$,</li> <li>pick a (random) permutation $\alpha$ of $\{1,2,\ldots,n\}$,</li> <li>draw edges from $a_i$ to $b_{\alpha(i)}$ for all $i \in \{1,2,\ldots,n\}$,</li> <li>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$.</li> </ul> <p>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).</p> <p>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.</p> <blockquote> <p><strong>Question</strong>: Given a bipartite multigraph, in how many ways could it have been generated by the above process?</p> </blockquote> <p>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, <a href="http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291098-2418%28199707%2910%3A4%253C487%3A%3AAID-RSA4%253E3.0.CO;2-Q/abstract" rel="nofollow">Sampling Contingency Tables</a>, Random Structures &amp; Algorithms 10 (1997), 487–506.</p> <p>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.</p> <p>This leads me to the sub-questions:</p> <blockquote> <p><strong>Sub-question</strong>: Is there an efficient way to compute these numbers (other than some kind of backtracking algorithm)?</p> </blockquote> <p>and</p> <blockquote> <p><strong>Sub-question</strong>: Does there exist a graph whose automorphisms correspond (naturally) to the different ways of generating a given bipartite multigraph by the above method?</p> </blockquote> <p>If it is possible to do the above, then we could use e.g. <a href="http://cs.anu.edu.au/~bdm/nauty/" rel="nofollow">nauty</a> to compute it easily.</p> <p>(Note: This question is "the other side of the coin" of a math.SE question: <a href="http://math.stackexchange.com/questions/131722" rel="nofollow">What is the number of bijections between two multisets?</a> However, I tried to make this question self-contained.)</p> http://mathoverflow.net/questions/95011/in-how-many-ways-can-we-generate-a-given-bipartite-multigraph-via-the-bipartite-c/95016#95016 Answer by Zur Luria for In how many ways can we generate a given bipartite multigraph via the bipartite configuration model? Zur Luria 2012-04-24T12:07:54Z 2012-04-24T12:07:54Z <p>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?</p> <p>I think that your question is related to Barvinok's work on contingency tables. In particular, take a look at theorem 1.2 here: </p> <p><a href="http://www.math.lsa.umich.edu/~barvinok/newtab.pdf" rel="nofollow">http://www.math.lsa.umich.edu/~barvinok/newtab.pdf</a></p> <p>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)$.</p> <p>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$.</p> <p>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:</p> <p>$$\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}!}} .$$</p> <p>This counting argument is very well presented in Barvinok's paper.</p> http://mathoverflow.net/questions/95011/in-how-many-ways-can-we-generate-a-given-bipartite-multigraph-via-the-bipartite-c/95019#95019 Answer by Brendan McKay for In how many ways can we generate a given bipartite multigraph via the bipartite configuration model? Brendan McKay 2012-04-24T13:03:44Z 2012-04-24T13:03:44Z <p>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).</p>