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 ?

  • 1
    $\begingroup$ This might be a hard question and I suspect that the answer is very close to $0$ since bipartiteness implies a very special structure about the (random) adjacency matrix. $\endgroup$ – Sandeep Silwal Dec 25 '18 at 15:39

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks for the detailed answer. In the third item of your bulleted list, the first binomial coefficient should be $\binom{\binom{n}{2}-k}{m-k}$, correct ? $\endgroup$ – Teddy Dec 27 '18 at 8:16
  • $\begingroup$ @Teddy It should, yes. Thank you for the correction. With $k = O(\log n)$, the approximation holds either way. $\endgroup$ – Misha Lavrov Dec 27 '18 at 16:11
  • $\begingroup$ (The approximation that I quoted was wrong, and I've fixed it now, but the product was already correct.) $\endgroup$ – Misha Lavrov Dec 27 '18 at 19:28

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.