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

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(XY,p) be a random bipartite graph where the set of edges is XY, 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 E1E2, E1X and E2Y is a biclique if for each node xX and each node yY, there is an edge between x and y. The size of a biclique E1E2 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

Leave a Comment