4
$\begingroup$

How many distinct non-isomorphic bipartite graphs with parts of size $m$ and $n$ exist? (Two bipartite graphs are distinct if there is no way to just rearrange the vertices within a part set of one of them to become the other.) It's not necessary that every vertex has an edge. Is there a closed form formula in terms of $m$ and $n$? If not, is there a recursive way to count it? If there is a good recursive algorithm to count it, what would its pseudocode look like?

Thanks!

$\endgroup$
  • $\begingroup$ arxiv.org/pdf/1304.0139.pdf $\endgroup$ – HEKTO Jun 13 '17 at 23:30
  • $\begingroup$ I don't think species are needed though, it falls to simple polya. Although yeah, species are awesome :p $\endgroup$ – Jorge Fernández Hidalgo Jun 13 '17 at 23:31
  • $\begingroup$ How would I use Polya's theorem in this problem? Would I have to examine each of the $m!n!$ possible symmetries and count how many graphs are fixed by each one? That seems too complicated to find an effective way to count the number of such graphs. $\endgroup$ – Anon Jun 14 '17 at 1:08
  • 1
    $\begingroup$ This problem appeared at the following MSE link. Complexity is not factorial but rather the number of terms in the cycle index of the symmetric group (partition function). $\endgroup$ – Marko Riedel Jun 14 '17 at 1:34
  • 2
    $\begingroup$ Maybe you want oeis.org/A028657 $\endgroup$ – Gerry Myerson Jun 14 '17 at 1:55
2
$\begingroup$

On your question whether or not there exists a closed-form formula for the number of bipartite graphs with parts of size $m$ and $n$ (denoted by $|B_u(m,n)|$ below), my coauthor and I proved the following formulas for $m = 2$ and $m = 3$ in an upcoming paper. $|B_u(2,n)|$ corresponds to the integer sequence A002623, i.e., 1, 3, 7, 13, 22, 34, 50, 70, 95,..., and $|B_u(3,n)|$ corresponds to the integer sequence A002727, i.e., 1, 4, 13, 36, 87, 190, 386, 734, 1324, 2284,... in Sloane's classification of integer sequences. Generalizing these closed-form formulas for $m = 4,5,6,...$ remains an open problem to the best of my knowledge.

$$|B_u(2,n)|\!=\! \frac{2n^{3}+15n^{2} + 34n + 22.5 + 1.5\left ( -1 \right )^{n}}{24}, n=0,1,2,...$$

$\,$

$\!\!\!\!\!\!\!|B_{u}\left( 3,n \right)|\! = \left\{\begin{matrix} \frac{1}{6}\left [ \binom{n+7}{7}\! + \frac{3\left ( n+4 \right )\left ( 2n^{4}+32n^{3}+172n^{2} + 352n + 15\left ( -1 \right )^{n} +225 \right )}{960} +\! \frac{2(n^{3}+12n^{2}+45n+54)}{54} \right ] &\!\!\!\!\!\!\text{if}\, n \bmod\!\! \text{ } 3 = 0, \\ \\ \frac{1}{6}\left [ \binom{n+7}{7}\! + \frac{3\left ( n+4 \right )\left ( 2n^{4}+32n^{3}+172n^{2} + 352n + 15\left ( -1 \right )^{n} +225 \right )}{960} +\! \frac{2(n^{3}+12n^{2}+45n+50)}{54} \right ] &\!\!\!\!\!\!\!\text{ if}\, n \bmod\!\! \text{ } 3 = 1, \\ \\ \frac{1}{6}\left [ \binom{n+7}{7}\! + \frac{3\left ( n+4 \right )\left ( 2n^{4}+32n^{3}+172n^{2} + 352n + 15\left ( -1 \right )^{n} +225 \right )}{960} +\! \frac{2(n^{3}+12n^{2}+39n+28)}{54} \right ] &\!\!\!\!\!\!\!\!\! \text{if}\, n \bmod\!\! \text{ } 3 = 2. \!\!\!\! \end{matrix}\right. $

Ref: Abdullah Atmaca and A. Yavuz Oruc. "On The Size Of Two Families Of Unlabeled Bipartite Graphs." AKCE International Journal of Graphs and Combinatorics. To appear.

$\endgroup$
1
$\begingroup$

In a more recent article by A. Atmaca and A. Yavuz Oruc, the following more general result for the number of unlabeled graphs with $n$ left vertices and $r$ right vertices (denoted by $|B_u(n,r)|$) has been proven:

$$\frac{{r+2^n-1\choose r}}{n!}\le |B_u(n,r)| \le 2\frac{{r+2^n-1\choose r}}{n!}, n < r. $$

Given that $|B_u(n,r)|= |B_u(r,n)|$, the following inequality holds as well when $n > r:$

$$\frac{{n+2^r-1\choose n}}{r!}\le |B_u(n,r)| \le 2\frac{{n+2^r-1\choose n}}{r!}, n > r. $$

Note that the upper bound is twice as large as the lower bound. Tightening the constant factors, i.e., 1 and 2 on the lefthand and righthand side of the inequality remains open.

$\endgroup$
  • $\begingroup$ When $r=n$ are isomorphisms allowed to swap the two partite sets? $\endgroup$ – bof Jul 14 '18 at 10:00
  • 1
    $\begingroup$ In these formulas, it is assumed that left and right sets of vertices are not swappable whether or not $n = r$ as in Harrison, Michael A. "On the number of classes of binary matrices." IEEE Transactions on Computers 100.12 (1973): 1048-1052. For example, if $n = r = 2$ with left set of vertices denoted $X = \{x_1,x_2\}$ and right set of vertices denoted $Y = \{y_1,y_2\}$, the graph that connects $x_1$ to $y_1$ and $y_2$ and the graph that connects $y_1$ to $x_1$ and $x_2$ are considered non-isomorphic. $\endgroup$ – AYO Jul 14 '18 at 15:07
  • $\begingroup$ It should also be added that the lower bounds in the two inequalities coincide and also hold when $n = r$ under the same assumption as in my earlier comment. $\endgroup$ – AYO Jul 14 '18 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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