MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am discovering random graph and I am trying to prove the following result. This is a follow-up on a previous question of mine

what's an upper bound on the size of the largest biclique in random bipartite graph?

Let G(X∪Y,p) be a random bipartite graph where the set of vertices is X∪Y, X and Y both have cardinality n and p is the proba of adding an edge between each node in X and each node in Y. p∈(0,1) is independent of $n$. A set $E_1∪E_2$, $E_1⊂X$ and $E_2⊂Y$ is a biclique if for each node $x∈X$ and each node $y∈Y$, there is an edge between $x$ and $y$.

Let $E=E_1∪E_2$ be a biclique satisfying ${Expectation}(∣E_1∣) \leq {Expectation}(∣E_2∣)$. The conjecture is that

for all α>0, Pr{∣E_1∣ is greater than α×n}→0 as n→∞.

Could any of you help me on this?

Thanks a lot!

If instead of requiring ${Expectation}(∣E_1∣) \leq {Expectation}(∣E_2∣)$, I were to focus on balanced biclique, i.e., require $∣E_1∣ = ∣E_2∣$, then the result is already known. Clearly, the result would also hold if I were to assume that $∣E_1∣ \leq ∣E_2∣$ (given that from such a biclique, I could "extract" a balanced biclique of size $∣E_1∣$).


share|cite|improve this question
I'm having trouble parsing "Let $E$ be a biclique satisfying $\mathbb{E}(|E_1|) \leq \mathbb{E}(|E_2|)$." Could you perhaps clarify what you mean? – Ben Barber Dec 11 '12 at 16:12
Sure. I am not entirely sure this makes sense but what I wanted is to consider $E=E_1 \cup E_2$ where E is a biclique -- E is a random variable and, hence, so are $E_1$ and $E_2$. So I wanted to impose the constraint on those r.v. that $Expectation(|E_1|)≤Expectation(|E_2|)$ and hence restrict my attention only to bicliques $E=E_1 \cup E_2$ having the property that $Expectation(|E1|)≤Expectation(|E2|)$. Does this answer? – Oliver Dec 11 '12 at 17:35
"$E$ is a random variable": How is $E$ determined from the random graph? – Ben Barber Dec 11 '12 at 21:55
For each realization of the random (bipartite) graph, one can pick an arbitrary E which is a biclique. By definition, $E=E_1 \cup E_2$. Seen as a random set, E defines my r.v. Of course, there are plenty of different r.v. to be considered (depending on which one we pick above). The only constraint I would like to impose is that $Expectation(|E_1|)≤Expectation(|E_2|)$. I'd like the statement in the Question to be true for all such r.v. E (i.e., for all α>0, Pr{∣E_1∣ is greater than α×n}→0 as n→∞). Hope this answers... – Oliver Dec 11 '12 at 22:11
cross-posted to – joriki Dec 12 '12 at 16:25
up vote 0 down vote accepted

Thanks for the clarification. This set-up has enough flexibility that we can recover the star counterexample from before.

Almost every random graph has a vertex in each class of degree about $pn$. So we can almost always choose $E$ to be a large star, and we can ensure the centre of the star is in each class about equally often. Then the expectations of the class sizes are almost equal, so with a bit of tweaking we satisfy the condition on the choice of $E$; but $E_1$ will be too large with probability almost $1/2$.

share|cite|improve this answer
Thanks a lot Ben. This makes perfect sense! – Oliver Dec 12 '12 at 0:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.