Probability that a graph is bipartite

Question

Given the empty graph on $n$ vertices, we add $m$ of the $\binom{n}{2}$ possible edges, uniformly at random.

What is the probability that the resulting graph is bipartite (equivalently, contains no odd cycles) ?

Alternative formulation: In the random graph model $G(n,m)$, how many of the $\binom{\binom{n}{2}}{m}$ graphs are bipartite ?

Answer 1

When $m \ll n$, the probability is very high, since with high probability (that is, with probability tending to $1$) $G(n,m)$ is a forest - and all forests are bipartite.

When $m = \frac12 cn$ (where $G(n,m)$ is very like a binomial random graph with edge probability $\frac cn$) much depends on the value of $c$. If $0 < c < 1$, we are in the subcritical phase where, with high probability, the largest component of the random graph has $O(\log n)$ vertices. Therefore we may determine if the graph is bipartite by counting the small cycles.

The expected number of cycles of length $k$ is asymptotically $\frac{c^k}{2k}$, obtained by multiplying together the following factors:

• We have $\binom nk \sim \frac{n^k}{k!}$ ways to choose $k$ vertices.
• There are $\frac{k!}{2k}$ ways to choose a cycle on those $k$ vertices.
• There is a probability of $\binom{\binom n2-k}{m-k} / \binom{\binom n2}{m} \sim \frac{c^k}{n^k}$ that all edges in that cycle are present. (This is the approximation that requires $k$ to be small; here, we have $k = O(\log n)$, but any $k = o(n)$ would do.)

It can be shown by the method of moments that the number of cycles of length $k$ is asymptotically Poisson (explained by the intuition that cycles arise from many nearly-independent events which are individually very unlikely). So the probability that there are no cycles of length $k$ is $e^{-c^k/2k}$ in the limit.

It would need more justification, but it is probably true that these events are asymptotically independent as $n \to \infty$. This means that the probability that $G(n,m)$ is bipartite is obtained by taking the product of these probabilities $$ \exp\left(-\frac{c^3}{6} - \frac{c^5}{10} - \frac{c^7}{14} - \dots\right) = \exp\left(\frac12c - \frac12 \operatorname{arctanh} c\right). $$ This probability tends to $0$ as $c \to 1$, and so by monotonicity we see that when $m = \frac12cn$ and $c>1$, the graph is not bipartite with high probability.

Intuitively, at this point, we are in the supercritical phase; the number of cycles (some of them quite long) tends to infinity, and since there is no particular reason forcing them to be even, it is likely that many of them are odd.