Question

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

Given a bipartite graph G=(V₁ ∪ V₂, e) where |V₁|=|V₂| and a probability p of there being an edge from any a ∍ V₁ to any b ∍ V₂, 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 2ⁿ unique subsets, the empty set and the entire set not included, leaves 2ⁿ-2 subsets. Therefore there can be at most 2ⁿ-2 maximal bicliques. This upper bound is achievable when there are n²-n edge (I can prove this if anyone wants me to).

Both of these results are also easily extended to bipartite graphs where |V₁| ≠|V₂|.

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.

Answer 1

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".

Answer 2

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.

Answer 3

One approach might be as follows (I will assume your initial graph had n vertices on each side):

Given a subset S of size s on one side, and a subset T of size t on the other side, what is the probability it is a maximal clique? We need two things to happen.

1. It must be a clique. This occurs with probability p^{ab}.

2. No vertex outside the clique is connected to all the vertices inside the clique on the appropriate side. For any given vertex, this occurs with probability (1-p^{n-a}) or (1-p^{n-b}), depending on which side it needs to fail to connect to. The handy thing is that everything in sight is independent here, so we can just multiply over all vertices outside the clique.

Multiplying, the probability SXT is a maximal clique is p^{ab} (1-p^{n-a})^b (1-p^{n-b})^a. Now by linearity of expectation you just need to add up over all subsets, and (possibly) work out the asymptotics as n tends to infinity.