5
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – D. Chen
    Oct 16 '13 at 16:13
  • $\begingroup$ 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). $\endgroup$
    – dtldarek
    Oct 16 '13 at 16:48
  • $\begingroup$ Good point, @dtldarek ! I will try it this way. $\endgroup$
    – D. Chen
    Oct 16 '13 at 17:03
  • $\begingroup$ @dtldarek I tried it but failed. Can you give me more hints? $\endgroup$
    – D. Chen
    Oct 16 '13 at 21:01
  • 1
    $\begingroup$ 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). $\endgroup$
    – dtldarek
    Oct 16 '13 at 22:41
5
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – D. Chen
    Oct 16 '13 at 17:02
  • 1
    $\begingroup$ @TomSmith I've done some updating; see if you can take it from there. I'll check back in with it later. $\endgroup$ Oct 16 '13 at 18:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – D. Chen
    Oct 16 '13 at 19:38
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 16 '13 at 20:00
  • $\begingroup$ 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. $\endgroup$
    – D. Chen
    Oct 16 '13 at 20:53

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.