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∪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. I am interested in the (expected) size of the largest biclique (not necessarily balanced!). To be more precise, a set E1∪E2, E1⊂X and E2⊂Y is a biclique if for each node x∈X and each node y∈Y, there is an edge between x and y. The size of a biclique E1∪E2 is ∣E1∣+∣E2∣.

Let E be a biclique. The conjecture is that

- for all α>0, Pr{E has size greater than α×n}→0 as n→∞.
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**

For every vertex x in G, have star(x) denote the set whose members are x and the vertices adjacent to x.

For every vertex x in G, star(x) is a biclique of size deg(x)+1. The degrees of vertices in

X are independent and distributed as Bin(n,p). From the central limit theorem, if α≤p

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

size greater than α⋅n will be less than 23. If α≤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 α⋅n converges to 0.

Therefore, if α≤p then lim.

**Attribution***Source : Link , Question Author : Oliver , Answer Author : Community*