We can use an n*m 0-1 matrix to denote a bipartite graph. Mining maximal bicliques in such matrix is an open problem.
The extreme maximal clique is a special maximal clique. A clique in such matrix is itself a all 1 submatrix. We differentiate two parts of a clique as a major part in row-view of the matrix and a minor part in column-view. A clique is an extreme maximal one if and only if it satisfies: (1) no other clique has bigger cardinality with major part than that of it; (2) if with the same major cardinality, then no other clique has bigger cardinality with minor part than that of it; (3) the minor cardinality is not less than a specified value s.
Extreme maximal bicliques is very rare by experimental results. However, we do not know what relation between the number of extreme maximal bicliques and n,m.
The problem is how many extreme maximal bicliques are in an n*m 0-1 matrix at most.
An example as a 4*4 matrix below, if s=2, then the row 1,2,3 and the column 1,2 make an extreme biclique with major cardinality 3 minor cardinality 2, and there are only 2 such bicliques in the matrix. 1 1 1 1
1 1 0 0
1 1 0 1
1 0 0 1
For an nm 0-1 matrix, if the size of so-called extreme maximal biclique (EMB) is 11, then there are at most min(n,m) EMBs in the matrix. We can construct such case matrix with the most many EMBs as below:
1 0 0 0 0 0 0 ......
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
......
And I guess that it holds that there are at most max(n,m) EMBs in an n*m 0-1 matrix.