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

arXiv0708.1174MaRDI QIDQ6206447FDOQ6206447

Publication date: 8 August 2007

Abstract: 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, Hromkoviv{c}, Schnitger (1994). We also give examples for which fool ge (rk)^{log_4 6} improving on Dietzfelbinger et al.

Mathematics Subject Classification ID

Communication theory (94A05) Positive matrices and their generalizations; cones of matrices (15B48) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: On some lower bounds on the number of bicliques needed to cover a bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6206447)