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

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

2007-08-08

arxiv.org/abs/0708.1174v4

Mathematics

Combinatorics

6 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On some lower bounds on the number of bicliques needed to cover a bipartite graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On some lower bounds on the number of bicliques needed to cover a bipartite graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On some lower bounds on the number of bicliques needed to cover a bipartite graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-416762