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

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

2012-12-07T21:45:28Z

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!

Answer by Ricky Demer for what's an upper bound on the size of the largest biclique in random bipartite graph?

2012-12-07T22:16:48Z

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