How many connected bipartite graphs are there?

Question

I am trying to determine how rare (connected) bipartite graphs are among all (connected) graphs with the same number of nodes.

Because this is an open-ended question, there are many ways to formalize it. One way is: suppose you have a graph with nodes labeled $1\ldots n$, and you generate edges of the graph uniformly at random. What is the probability $p(n)$ that the resulting graph is bipartite? What is the asymptotic behavior of $p(n)$ as $n$ becomes large?

I have attempted to set up a recurrence relation, describing $p(n+1)$ in terms of $p(n)$, but haven't found any obvious simple form. I have also considered the restriction of this problem to graphs that are connected, but then I don't know what "uniform distribution" would make sense over the set of all connected graphs on $n$ nodes.

Is this probability easy to compute? Is there a typical technique that can help me, or some references I should look at? I suspect bipartite graphs are rare among connected graphs—does that sound intuitively right? This is unknown territory for me.

Answer 1

The probability that the uniform random graph will be bipartite is in fact extremely low.

It is not straightforward to compute exactly, because there is a large number of ways for it to happen, and they are all dependent events. But we can get a pretty good upper bound without too much suffering.

Consider: for each partition $(A,B)$ of the vertex set, the probability that it's a bipartition is $(\frac12)^{\binom{|A|}{2}} \cdot (\frac12)^{\binom{|B|}{2}}$. That's the probability that there are no edges between two vertices in $A$, and no edges between two vertices in $B$. Given $|A|+|B|=n$ (the total number of vertices), the quantity $\binom{|A|}{2} + \binom{|B|}{2}$ is minimized when $|A| \approx |B|$; we'll take $|A|=|B|=\frac n2$, for $2\binom{n/2}{2} = \frac14 n(n-2)$ edges. In other words, the probability that $(A,B)$ is a bipartition is always less that $2^{-\frac14 n(n-2)}$.

There are $2^{n-1}$ ways to choose the bipartition $(A,B)$, up to swapping $A$ and $B$, so we have $2^{n-1}$ different probabilities of $2^{-\frac14 n(n-2)}$. The probability that any of these events happens is at most the sum of these probabilities - less, because they're not disjoint. This gives us an upper bound of $2^{(n-1) - \frac14n(n-2)} = 2^{-\frac14(n^2-6n+4)}$.

How good is this upper bound? Well, there are two sources of error:

• Not all $2^{n-1}$ pairs $(A,B)$ have $|A|=|B|=\frac n2$. However, when $n$ is even, there are $\binom{n-1}{n/2-1}$ such pairs, which is approximately $2^{n-1} \cdot \sqrt{\frac{2}{\pi n}}$; something roughly similar happens for odd $n$. The factor of $\sqrt{\frac{2}{\pi n}}$ is insignificant compared to the exponentials we've got.
• These events are not all disjoint. However, because these probabilities are so tiny, treating them as disjoint is a good approximation. (For a lower bound on the probability, we could treat them as independent, because they're actually positively correlated, and that gives approximately the same bound.)

Anyway, with a probability of at most (and very close to) $2^{-\frac14(n^2-6n+4)}$ that the random graph is bipartite, we compute that out of the $2^{\binom n2}$ possible random graphs, at most (and very close to) $2^{\binom n2 -\frac14(n^2-6n+4)}$ or $2^{n^2/4 + n -1}$ are bipartite.

I realize now that I forgot to specify "connected", but it's also true that it's very unlikely for a random graph to be disconnected, and the same estimate still works.

That's for large $n$; for small $n$, see sequence A001832 in the OEIS.