Probability that graph is bipartite in Erdős–Rényi model with constant probability.

Question

Given $G(n,p)$ where $p$ is constant, how could we determine the probability that the random graph is bipartite? I have seen the approach shown here but I don't fully understand why setting $|A| = |B| = n$ is correct (although in my case, they would have size $\frac{n}{2}$ I guess), as the disjoint vertex sets don't have to have the same number of elements necessarily.

Answer 1

In the linked question they specified two bipartition sets of size $n$ in advance. If you don't specify the bipartition sets, then it seems very hard to me. Even in the case $p=\frac12$ where all graphs have the same probability, you're asking how many labelled graphs on $n$ vertices are bipartite.

A005142 lists the number of connected bipartite graphs on $n$ vertices for $n\leq24$, and you can see that the number gets very large very quickly. With $p=\frac12$, we find that the probability that a random graph with $24$ nodes is connected and bipartite is $$\frac{101386021137641794979558045}{2^{276}}\approx8.35\cdot10^{-58}$$

EDIT

According to the accepted answer on this question on Math Overflow, the number of triangle-free graphs on $n$ vertices is $2^{n^2(1/4 +o(1)) }$ and the number of bipartite graphs with a fixed pair of parts of size $n/2$ is of order $2^{n^2/4}$. Since a bipartite graph is triangle-free, we can say that the number of bipartite graphs is of order $2^{n^2(1/4 +o(1)) }$. Of course, the number of labelled graphs is of order $2^{n^2/2}$ so we can estimate the probability in the $p=\frac12$ case.