1
$\begingroup$

I have attempted to calculate the number of unlabelled bipartite graphs as follows:

Let $G = (V_1, V_2, E)$ be a bipartite graph on $n$ vertices with $|V_1| = m$ and $|V_2| = n-m$. Assume without loss of generality that $|V_1| \leq |V_2|$ so $m \leq \left\lfloor \frac{n}{2} \right\rfloor$. If $G$ is complete bipartite then it has $m(n-m)$ edges since each of the vertices in $V_1$ is connected to each in $V_2$. Thus, the total number of bipartite graphs with parts of size $m$ and $n-m$ is $2^{m(n-m)}$. In order to find the total number of possible bipartite graphs on $n$ vertices we sum over all possible $m$: \begin{align} \sum^{\left\lfloor \frac{n}{2} \right\rfloor}_{m=1} 2^{m(n-m)} \end{align}

However, I notice that I have counted labelled bipartite graphs where I need the number of unlabelled graphs. I'm struggling to see how to account for this.

$\endgroup$
4
  • $\begingroup$ oeis.org/A033995 $\endgroup$ Feb 3, 2013 at 15:46
  • $\begingroup$ oeis.org/A005142 $\endgroup$ Feb 3, 2013 at 15:47
  • $\begingroup$ In the limit for large $n$, the average graph has no automorphisms, so the number of unlabeled graphs is simply the number of labeled graphs divided by the number of possible labelings, i.e. $n!$. $\endgroup$ Feb 3, 2013 at 17:39
  • $\begingroup$ It look to me that the given counting for labeled bipartite graphs is incorrect. Labeling of vertices does not imply particular partition of the vertices into V_1 and V_2. E.g., an isolated vertex may be viewed as belonging to V_1 or V_2 but that does not change the graph. $\endgroup$ Feb 4, 2013 at 2:55

4 Answers 4

3
$\begingroup$

It seems that what Andrew wants to count are what are called in enumerative contexts "bicolored graphs". A bicolored graph is a graph in which the vertices have been colored black and white so that every edge joins two vertices of different colors. A bipartite (or bicolorable) graph is a graph that has a bicoloring. A bicolorable graph with $k$ connected components has $2^k$ bicolorings. (In nonenumerative contexts the distinction between bipartite and bicolored is usually unimportant.) In addition, in counting bicolored graphs one might or might not consider switching the two colors to give an equivalent graph. All of the versions of the enumeration problem have been solved. Counting unlabeled bicolored graphs (with no color-switching equivalence) is a straightforward application of Burnside's lemma; counting unlabeled bipartite graphs is tricky.

It's not too hard to find appropriate references by searching MathSciNet. (Hint: "color" is sometimes spelled "colour".)

Incidentally, the number of labeled bicolored graphs on $n$ vertices is $$\sum_{m=0}^n 2^{m(n-m)}\binom{n}{m}.$$

$\endgroup$
1
$\begingroup$

The answer to your problem is detailed in the Thesis of Ji Li (2007) Counting Prime Graphs and Point-Determining Graphs Using Combinatorial Theory of Species http://people.brandeis.edu/~gessel/homepage/students/jilithesis.pdf

Section 4.4. p.112 The formulae are to be found p.115.

$\endgroup$
1
  • $\begingroup$ The published version of this part of Li's thesis is I. M. Gessel and J. Li, Enumeration of point-determining graphs, J. Combinatorial Theory Ser. A 118 (2011), 691-612. But the formula we give in this paper for the cycle index series for bicolored graphs isn't really new, I don't think; certainly the formula for unlabeled bicolored graphs that you get from it isn't new (and this isn't the point of our paper). But the paper does have references to earlier work on this topic. $\endgroup$
    – Ira Gessel
    Feb 6, 2013 at 17:24
1
$\begingroup$

In a forthcoming paper by A. Atmaca and A. Yavuz Oruc, it has been proved that the number of unlabeled graphs with $n$ left vertices and $r$ right vertices (denoted by $|B_u(n,r)|$) satisfies the following inequality

$$\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.

The same authors also provided the following exact formulas for $|B(n,r)|$ when $n = 2$ and $n = 3.$

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

$\,$

$|B_{u}\left(3,r \right)|\! = \left\{\begin{matrix} \frac{1}{6}\left [ \binom{r+7}{7}\! + \frac{3\left ( r+4 \right )\left ( 2r^{4}+32r^{3}+172r^{2} + 352r + 15\left ( -1 \right )^{r} +225 \right )}{960} +\! \frac{2(r^{3}+12r^{2}+45r+54)}{54} \right ] &\!\!\!\!\!\!\text{if}\, r \bmod\!\! \text{ } 3 = 0, \\ \\ \frac{1}{6}\left [ \binom{r+7}{7}\! + \frac{3\left ( r+4 \right )\left ( 2r^{4}+32r^{3}+172r^{2} + 352r + 15\left ( -1 \right )^{n} +225 \right )}{960} +\! \frac{2(r^{3}+12r^{2}+45r+50)}{54} \right ] &\!\!\!\!\!\!\!\text{ if}\, r \bmod\!\! \text{ } 3 = 1, \\ \\ \frac{1}{6}\left [ \binom{r+7}{7}\! + \frac{3\left ( r+4 \right )\left ( 2r^{4}+32r^{3}+172r^{2} + 352r + 15\left ( -1 \right )^{r} +225 \right )}{960} +\! \frac{2(r^{3}+12r^{2}+39r+28)}{54} \right ] &\!\!\!\!\!\!\!\!\! \text{if}\, r \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. https://doi.org/10.1016/j.akcej.2017.11.008.

$\endgroup$
0
$\begingroup$

In the formalism of species of structure. The species $Bip(X,Y)$ of bipartite graphs on two sorts of vertex $X$ and $Y$ can be described as, $$ Bip(X,Y) \simeq E^2 \circ (E^\bullet(X) E^\bullet(Y)) \simeq E^2 \circ (XY E(X + Y)) $$ where $E$ is the species of sets, $\circ$ is the functorial composition of species and $\bullet$ is the pointing operator.

If I make no mistake the series you search is, $$ Bip(x,y) = \prod_{k \ge 1}\exp\left[\frac{2}{k}x^ky^k\prod_{l \ge 1} \exp\left(\frac{1}{l}(x^{kl}+y^{kl}) \right)\right] $$

Hope this helps.

Edit : Doing the computations I find, \begin{align*} Bip(xt,yt) &= 1+2xy{t}^{2}+ \left( 2y{x}^{2}+2{y}^{2}x \right) {t}^{3}+ \left( 5{y}^{2}{x}^{2}+2y{x}^{3}+2{y}^{3}x \right) {t}^{4} + ... \end{align*} which is wrong. For example we should have $x^2 + y^2 +2xy$ in front of $t^2$, a $xt$ term as well as a $yt$ term..

$\endgroup$
1
  • $\begingroup$ I've checked the combinatorial description which is ok (the isomorphisms of species) The computation is wrong and I 'm not sure how to do it right. There is a description of the functorial composition of species in the book on species but it is hard to work out. $\endgroup$ Feb 5, 2013 at 19:05

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.