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. 



What is the expected number of maximal bicliques in a random bipartite graph?
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". 


