show/hide this revision's text 3 added 3 characters in body

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

http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra

Let G(X∪Y,p) be a random bipartite graph where the set of edges 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∣$).

Oliver
show/hide this revision's text 2 added 8 characters in body

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

http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra

Let G(X∪Y,p) be a random bipartite graph where the set of edges 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=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∣$).

Oliver
show/hide this revision's text 1

expected size of unbalanced biclique in random bipartite graph

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

http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra

Let G(X∪Y,p) be a random bipartite graph where the set of edges 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$ 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∣$).

Oliver