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


  • $\begingroup$ 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? $\endgroup$
    – Ben Barber
    Dec 11 '12 at 16:12
  • $\begingroup$ 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? $\endgroup$
    – Oliver
    Dec 11 '12 at 17:35
  • $\begingroup$ "$E$ is a random variable": How is $E$ determined from the random graph? $\endgroup$
    – Ben Barber
    Dec 11 '12 at 21:55
  • $\begingroup$ 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... $\endgroup$
    – Oliver
    Dec 11 '12 at 22:11
  • $\begingroup$ cross-posted to math.stackexchange.com/questions/256598 $\endgroup$
    – joriki
    Dec 12 '12 at 16:25

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


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.