# 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!

• Actually I think it doesn't matter whether the graph is directed. I just add it as a condition in case it makes some difference. Oct 16 '13 at 16:13
• You could also try to calculate the probability that there is a triangle in the graph, it might be enough (i.e. the probability may tend to 1). Oct 16 '13 at 16:48
• Good point, @dtldarek ! I will try it this way. Oct 16 '13 at 17:03
• @dtldarek I tried it but failed. Can you give me more hints? Oct 16 '13 at 21:01
• I've tried some basic methods and those didn't work. Before playing with variance I did a simple search and found that someone have writen such argument already. You might want to tweak a bit, because you have a bit more dependencies (e.g. if vertex has $s$ neighbors, then it cannot form triangles with new vertices), but surely that article is a nice start. Sorry I can't help you more, but I'm a bit time-constrained (and it's already 0:40am in my timezone). Oct 16 '13 at 22:41

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$.

• Thanks a lot Nicholas. I did something similar but was stuck on simplifying the sum without threatening the goal. Can you kindly help me on this step? Oct 16 '13 at 17:02
• @TomSmith I've done some updating; see if you can take it from there. I'll check back in with it later. Oct 16 '13 at 18:53
• Hi Nicholas. Thank you! I have question on the probability of ($v$ chooses no neighbors in $A$). I agree there are $\binom{b+s-1}{s-1}$ ways, but I think each way might not have equal probability. My probability of ($v$ chooses no neighbors in $A$) is simply $\left(\frac{b}{n}\right)^s$. If this is true, the calculation will be simplified a lot. Oct 16 '13 at 19:38
• @TomSmith Well, that all depends: does the order in which the neighbors are chosen matter? If it doesn't, then I'm right; if it does, then you're right. Oct 16 '13 at 20:00
• Hi Nicholas. I am sorry I didn't express clearly in my question. A vertex chooses each neighbor uniformly and independently. So a vertex chooses its neighbors one by one. I have edited my question to make it more clear. Oct 16 '13 at 20:53