# How many distinct non-isomorphic bipartite graphs with parts of size $m$ and $n$ exist?

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!

• arxiv.org/pdf/1304.0139.pdf – HEKTO Jun 13 '17 at 23:30
• I don't think species are needed though, it falls to simple polya. Although yeah, species are awesome :p – Jorge Fernández Hidalgo Jun 13 '17 at 23:31
• 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. – Anon Jun 14 '17 at 1:08
• 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). – Marko Riedel Jun 14 '17 at 1:34
• Maybe you want oeis.org/A028657 – Gerry Myerson Jun 14 '17 at 1:55

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.

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.

• When $r=n$ are isomorphisms allowed to swap the two partite sets? – bof Jul 14 '18 at 10:00
• 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. – AYO Jul 14 '18 at 15:07
• 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. – AYO Jul 14 '18 at 15:13