Probability of a random graph being bipartite We start from an "empty" graph with $n$ vertices standing alone. Each vertex has $s$ chances to choose one vertex each chance as its neighbor, uniformly and independently from the $n$ vertices, including itself, with replacement. A vertex chooses its neighbors one by one. So a vertex can choose itself, and can choose a vertex many times. The graph is directed so if $u$ chooses $v$ but $v$ doesn't choose $u$, then $(u,v)\in E$ but $(v,u) \not\in E$ . $s \ge 2$ is a constant integer. 
I want to show when $n\to +\infty$, it is unlikely that we will get a bipartite graph. That is, for $G(V,E)$, $\exists A \subset V$, all edges in $E$ are between $A$ and $V-A$ and no edge in $E$ is inside $A$ or inside $V-A$, which should be unlikely.
I did some experiments with MATLAB and it seems the probability could be exponentially small. (Please don't be effected by my result, it could be wrong.) However, I only want to show it goes to $0$ faster than $O(n^{-1})$.
Thank you! 
 A: The usual way to do this is as follows:
Suppose that your graph IS bipartite.  Then there is a partition $[n]=A\cup B$, $A\cap B=\varnothing$, such that all edges in the graph have one end in $A$ and one end in $B$. 
Let $S$ be the number of such partitions -- that is, the number of ways we can write $[n]=A\cup B$, $A\cap B=\varnothing$, such that there are no edges inside $A$ and no edges inside $B$. Then the probability that your graph is bipartite is precisely $P(S>0)$.  But, by Markov's inequality, we know that
$$
P(S>0)=P(S\geq 1)\leq\frac{\mathbb{E}[S]}{1}=\mathbb{E}[S],
$$
where $\mathbb{E}$ denote the expectation. But, since expectations break up over addition, we have
$$
\mathbb{E}[S]=\sum_{\substack{[n]=A\cup B\\A\cap B=\varnothing}}P(\text{no edges within $A$ or $B$}).
$$
Consider this probability.  This is equivalent to saying "No vertex in $A$ chooses a neighbor in $A$ and no vertex in $B$ chooses a neighbor in $B$".  Since the choices are made independently, this simplifies a lot:
$$
P(\text{no edges within $A$ or $B$})=\prod_{v\in A}P(\text{$v$ chooses no neighbors in $A$})\cdot\prod_{v\in B}P(\text{$v$ chooses no neighbors in $B$})
$$
For a fixed $v$ and a fixed set $A$, 
$$
P(\text{$v$ chooses no neighbors in $A$})=\frac{\binom{b+s-1}{s-1}}{\binom{n+s-1}{s-1}},
$$
where $\newcommand{\order}[1]{\lvert #1 \rvert}b:=\order{B}$. Why?  Because $v$ not choosing elements of $A$ means that it only chooses elements of $B$; the number of ways to choose $s$ elements from $b$, with replacement, is $\binom{b+s-1}{s-1}$. Etc.
We get a simiar result for $v\in B$, except using $a:=\order{A}$ in place of $b$. So, this says
$$
\begin{align*}
\mathbb{E}[S]&=\sum_{a+b=n}\sum_{\substack{[n]=A\cup B\\\order{A}=a,\order{B}=b}}\left[\frac{\binom{a+s-1}{s-1}}{\binom{n+s-1}{s-1}}\right]^b\left[\frac{\binom{b+s-1}{s-1}}{\binom{n+s-1}{s-1}}\right]^a\\
&=\binom{n+s-1}{s-1}^{-n}\sum_{a+b=n}\sum_{\substack{[n]=A\cup B\\\order{A}=a,\order{B}=b}}\binom{a+s-1}{s-1}^b\binom{b+s-1}{s-1}^a\\
&=\binom{n+s-1}{s-1}^{-n}\sum_{a=1}^{n-1}\binom{n}{a}\binom{a+s-1}{s-1}^b\binom{b+s-1}{s-1}^a.
\end{align*}
$$
Here, we have used the fact that determining $a$ determines $b$, and determining $A$ determines $B$... and the fact that there are $\binom{n}{a}$ ways to choose $A$, given $a$.
