On some lower bounds on the number of bicliques needed to cover a bipartite graph

Dirk Oliver Theis

Published 2007-08-08, updated 2011-09-06Version 4

The biclique covering number of a bipartite graph G is the minimum number of complete bipartite subgraphs (bicliques) whose union contains every edge of G. In this little note we compare three lower bounds on the biclique covering number: A bound jk(G) proposed by Jukna & Kulikov (Discrete Math. 2009); the well-known fooling set bound fool(G); the "tensor-power" fooling set bound fool^\infty(G). We show jk \le fool le fool^\infty \le min_Q (rk Q)^2, where the minimum is taken over all matrices with a certain zero/nonzero-pattern. Only the first inequality is really novel, the third one generalizes a result of Dietzfelbinger, Hromkovi\v{c}, Schnitger (1994). We also give examples for which fool \ge (rk)^{log_4 6} improving on Dietzfelbinger et al.