what's an upper bound on the size of the largest biclique in random bipartite graph? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:41:31Z http://mathoverflow.net/feeds/question/115748 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra what's an upper bound on the size of the largest biclique in random bipartite graph? Oliver 2012-12-07T21:45:28Z 2012-12-07T22:16:48Z <p>I am not an expert in random graph but I need the following result and I couldn't find any reference on this.</p> <p>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$.</p> <p>Let $E$ be a biclique. The conjecture is that </p> <ul> <li>for all $\alpha>0$, Pr{E has size greater than $\alpha \times n$}$\rightarrow 0$ as $n \rightarrow \infty.$</li> </ul> <p>I guess there exist references on this or standard way to prove this. Could any of you help me on this?</p> <p>Thanks a lot!</p> http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra/115752#115752 Answer by Ricky Demer for what's an upper bound on the size of the largest biclique in random bipartite graph? Ricky Demer 2012-12-07T22:16:48Z 2012-12-07T22:16:48Z <p>For every vertex $x$ in $G$, have $\:\text{star}(x)\:$ denote the set whose members are $x$ and the vertices adjacent to $x$. <br> For every vertex $x$ in $G$, $\:\text{star}(x)\:$ is a biclique of size $\:\text{deg}(x)+1\;$. $\;\;$ The degrees of vertices in <br> $X$ are independent and distributed as $\:\text{Bin}(n,p)\;$. $\;\;$ From the central limit theorem, if $\: \alpha \leq p$ <br> then for sufficiently large $n$, the probability that any particular vertex's star is not a biclique of <br> size greater than $\: \alpha \cdot n \:$ will be less than $\frac23$. $\;\;$ If $\: \alpha \leq p \;$ then as $n$ goes to infinity the probability <br> that no star centered on a vertex in $x$ is a biclique of size greater than $\: \alpha \cdot n \:$ converges to $0$.</p> <p>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 \;\;\;\;\;$.</p>