A set coverage problem
This paper shows that with B = {1, 2, .... n}, the smallest k such that (B x B) - {(j, j) | j is an element of B} = boolean OR(k)(i=1)(C(i) x D(j)) is s(n), where s(n) is the smallest integer k such that n <= (left perpendicular k k/2 right perpendicular). This provides a simple set based formulation and a new proof of a result for boolean ranks (de Caen et al., 1981 [2]) and biclique covering of bipartite graphs (Berukov et al., 2008 [1]; Froncek et al., 2007 [5]), making these intricate results more accessible. (C) 2009 Elsevier B.V. All rights reserved.
boolean rank combinatorial problems bipartite covering sperner's theorem