# Probability that binomial random graph is bipartite

Let $G_{2n,p}$ be the binomial random graph on $2n$ vertices, i.e. a certain edge is within the graph with probability $p$.

What is the probability that a realization of $G_{2n,p}$ is bipartite with two vertex sets each of size $n$?

I think it should be

$$\mathbb P (G_{2n,p} \text{bipartite}) = (1-p)^{2 (n-1)!},$$

since within both disjoint vertex subsets no edge can exist, thus in each of the two subsets $(n-1)!$ edges do not exist.

Is this argument correct?

• No. The question does not distinguish which bipartition(s) makes the graph bipartite. Jun 22 '13 at 11:51

Not quite. Suppose you fix disjoint vertex sets, $A$ and $B$, where $|A|=|B|=n$, and wonder whether the random graph $G(2n,p)$ is bipartite with respect to the partition $A,B$. This random graph is bipartite with this partition if and only if there are no internal edges in $A$ and no internal edges in $B$. So $$P(G(2n,p) \text{ is bipartite with partition }(A,B)) = (1-p)^{2 {n \choose 2}},$$ because the number of absent edges in $A$ is ${n \choose 2}$ and number of absent edges in $B$ is ${n \choose 2}$ (rather than $(n-1)!$ as you have). A more difficult question is what is the probability that $G(2n,p)$ admits a bipartite partition with each vertex set of size $n$. A trivial upper bound (given by the union bound over all such partitions) is $$P(G(2n,p) \text{ has a (n,n)-bipartite partition})\leq {2n \choose n}(1-p)^{2{n \choose 2}}.$$