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!
Best Answer
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$.