Maximal Biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.
Given a bipartite graph G=(V1 ∪ V2, e) where |V1|=|V2| and a probability p of there being an edge from any a ∍ V1 to any b ∍ V2, 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 |e|/n nodes can be connected to completely to |e|/n other nodes, making one maximal biclique. Otherwise connect |e|/n nodes completely to |e|/n nodes and connect one node to |e| mod n nodes.
Upper Bound: There are 2n unique subsets, the empty set and the entire set not included, leaves 2n-2 subsets. Therefore there can be at most 2n-2 maximal bicliques. This upper bound is achievable when there are n2-n edge (I can prove this if anyone wants me to).
Both of these results are also easily extended to bipartite graphs where |V1| ≠|V2|.
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.