{
  "id": "0708.1174",
  "version": "v4",
  "published": "2007-08-08T21:06:24.000Z",
  "updated": "2011-09-06T09:46:27.000Z",
  "title": "On some lower bounds on the number of bicliques needed to cover a bipartite graph",
  "authors": [
    "Dirk Oliver Theis"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "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, Hromkovi\\v{c}, Schnitger (1994). We also give examples for which fool \\ge (rk)^{log_4 6} improving on Dietzfelbinger et al.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2011-09-06T09:46:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70",
      "94A05",
      "15B48"
    ],
    "keywords": [
      "bipartite graph",
      "lower bounds",
      "biclique covering number",
      "well-known fooling set bound fool"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0708.1174T"
    }
  }
}