Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 n*m 0-1 matrix, if the size of so-called extreme maximal biclique (EMB) is 1*1, 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.

share|improve this question
    
It would help if you posted an actual question in the body (not just in the title). Also it would help you to post a slightly larger example to demonstrate the difficulty of the problem, but one which could be worked out. It is clear that a poor upper bound is (m choose A) times (n choose B) for some value of A and B, but tightening this calls for more knowledge of combinatorial design theory than I think I possess. Gerhard "Ask Me Not About t-Designs" Paseman, 2012.12.15 –  Gerhard Paseman Dec 15 '12 at 18:40
    
Can the major cardinality be less than the minor cardinality? –  Ben Barber Dec 16 '12 at 12:18
    
The major cardinality is not related to the minor cardinality. The major may be less than the minor, only dependent on the matrix and the conditions of extreme maximal biclique (1), (2) and (3). –  liaomingxue Dec 23 '12 at 2:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.