I am not an expert in random graph but I need the following result and I couldn't find any reference on this.


Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup 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 \in (0,1)$ is independent of $n$. I am interested in the (expected) size of the largest biclique (not necessarily balanced!). To be more precise, a set $E\_1 \cup E\_2$, $E\_1 \subset X$ and $E\_2 \subset Y$ is a biclique if for each node $x \in X$ and each node $y \in Y$, there is an edge between $x$ and $y$. The size of a biclique $E\_1 \cup E\_2$ is $\mid E\_1 \mid + \mid E\_2 \mid$.


Let $E$ be a biclique. The conjecture is that 


* for all $\alpha>0$, Pr{E has size greater than $\alpha \times n$}$\rightarrow 0$ as $n \rightarrow \infty.$


I guess there exist references on this or standard way to prove this. Could any of you help me on this?


Thanks a lot!



what's an upper bound on the size of the largest biclique in random bipartite graph?
For every vertex $x$ in $G$, have $\:\text{star}(x)\:$ denote the set whose members are $x$ and the vertices adjacent to $x$.
  

For every vertex $x$ in $G$, $\:\text{star}(x)\:$ is a biclique of size $\:\text{deg}(x)+1\;$. $\;\;$ The degrees of vertices in
  

$X$ are independent and distributed as $\:\text{Bin}(n,p)\;$. $\;\;$ From the central limit theorem, if $\: \alpha \leq p$
  

then for sufficiently large $n$, the probability that any particular vertex's star is not a biclique of
  

size greater than $\: \alpha \cdot n \:$ will be less than $\frac23$. $\;\;$ If $\: \alpha \leq p \;$ then as $n$ goes to infinity the probability
  

that no star centered on a vertex in $x$ is a biclique of size greater than $\: \alpha \cdot n \:$ converges to $0$.


Therefore, if $\: \alpha \leq p \;$ then $\;\;\;\; \displaystyle\lim\_{n\to \infty} \: \text{Pr}\hspace{.01 in}(\text{the graph a a biclique with size greater than } \alpha \cdot n) \;\; = \;\; 1 \;\;\;\;\;$.


