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?

  • $\begingroup$ No. The question does not distinguish which bipartition(s) makes the graph bipartite. $\endgroup$ – Angela Richardson 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}}. $$


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.