# What is the expected number of maximal bicliques in a random bipartite graph?

Maximal Biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.

Given a bipartite graph $G=(V_{1}\cup V_{2}, E)$ where $|V_{1}|=|V_{2}|$ with probability $p$ of there being an edge from any $a\in V_{1}$ to any $b\in V_{2}$, what is the expected number of maximal bicliques?

What I have worked out is the upper and lower bounds:

Lower Bound: 1 or 2. If $|E|$ is divisible by $n$, then $\frac{|E|}{n}$ nodes can be connected to completely to $\frac{|E|}{n}$ other nodes, making one maximal biclique. Otherwise, connect $\frac{|E|}{n}$ nodes completely to $\frac{|E|}{n}$ nodes and connect one node to $|E|(mod\ n)$ nodes.

Upper Bound: There are $2^n$ unique subsets, the empty set and the entire set not included, leaves $2^n-2$ subsets. Therefore, there can be at most $2^n-2$ maximal bicliques. This upper bound is achievable when there are $n^2-n$ edges (I can prove this if anyone wants me to).

Both of these results are also easily extended to bipartite graphs where $|V_{1}|\neq |V_{2}|$.

The upper and lower bounds are both fairly trivial for the most part and it's the expected number of maximal bicliques that I've had the most trouble with. I've done a little work analyzing simple cases and brute forcing the expected number for small values of $n$ (I suppose I could write a program to brute force larger values of $n$), but it hasn't amounted to anything worth saying.

I'd appreciate any suggestions for methods of attacking the problem or references that I might find useful.

-

The expected clique number (i.e. size of the maximum clique) in a random graph (all edge probabilities = 1/2) is around 2log_2(n) where n is the number of vertices. You can find the proof in Alon and Spencer's "The Probabilistic Method", chapter 4. My guess is that a similar method would apply in the bipartite case, with a similar result. It also shouldn't be hard to extend the result to general p.

I you want to understand how to solve this kind of problems, I can't think of any better way than to carefully study the first few chapters of "The Probabilistic Method".

-

The "maximal clique" (as used by liberalkid) and the "maximum clique" (as used by Alon Amit) are not the same thing. A maximal clique is just a clique that's not contained in any larger clique. A single edge can be a maximal clique, and for p = C/n, where n is the number of vertices in the graph, I believe the number of size-1 maximal cliques approaches some constant as n gets large.

That being said, the methods of Alon and Spencer's book are probably still useful.

-
Bleah. Of course, sorry. –  Alon Amit Oct 14 '09 at 18:19