1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Dec 15, 2012 at 18:40
  • $\begingroup$ Can the major cardinality be less than the minor cardinality? $\endgroup$
    – Ben Barber
    Commented Dec 16, 2012 at 12:18
  • $\begingroup$ 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). $\endgroup$
    – liaomingxue
    Commented Dec 23, 2012 at 2:57

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .