A biclique is a complete bipartite graph. A graph is a "biclique collection" if it can be decomposed into the disjoint union of bicliques. Denote the set of such graphs by $\mathcal{BCC}$.

Given a graph $G=(V,E)$, are there any known bounds on $d(G,\mathcal{BCC})$? In particular, is it true that $d(G,\mathcal{BCC})<\alpha|E|$, for some constant $\alpha<1$?

  • $\begingroup$ And what is the distance function $d$? Also, "disjoint" means "vertex disjoint"? $\endgroup$ – JBL Dec 3 '10 at 19:31
  • $\begingroup$ I guess probably edit distance? Least number of edges in the symmetric difference of $G$ and some graph in BCC? $\endgroup$ – Louigi Addario-Berry Dec 3 '10 at 22:36
  • $\begingroup$ Distance is edit distance. Disjoint is vertex disjoint. Sorry for not being clear. $\endgroup$ – Jeremy H Dec 3 '10 at 23:09

I strongly doubt that there is any bound of the form $d(G,\mathcal{BCC})<\alpha|E|$ with $\alpha<1$. It is well known that for any degree d there are graphs which are regular of degree d and girth (length of the smallest cycle) greater than 4. Such a graph with large d would seem to be far from $\mathcal{BCC}$. I'd even conjecture (but with less confidence) that as the number of vertices goes to infinity, a random graph regular of degree d is at distance something like $\frac{d-3}{d}|E|$.

As a specific test case, let $n=2d-1$ and consider this graph $G$ with $\binom{2n}{n}$ vertices all of degree $d$: The vertices are the subsets of size $d-1$ and $d$ of $\lbrace 1,2,3,\cdots,n \rbrace$ and the edges are all $(A,B)$ with $A \subset B.$ It seems clear (although I have not spelled out a proof) that a biclique with large average degree will have a large proportion of its edges not in $G$ and a biclique with small average degree will miss a large proportion of the edges (of the subgraph of $G$ induced by its vertices)

  • 1
    $\begingroup$ Slightly tweaking your test case: Let $V=[n]^{d-1}\cup[n]^d$ and have edges for all $(u,v)$ with $u\subset v$ as ordered lists. The resulting graph has distance essentially $\frac{d-1}{d}|E|$. $\endgroup$ – Jeremy H Dec 6 '10 at 22:15
  • $\begingroup$ I agree. I don't see how one could do much better than to cover the vertices with stars which would give distance $\frac{d-1}{d}|E|$. $\endgroup$ – Aaron Meyerowitz Dec 7 '10 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.