# Graphs far from being a collection of bicliques

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$?

• And what is the distance function $d$? Also, "disjoint" means "vertex disjoint"? – JBL Dec 3 '10 at 19:31
• I guess probably edit distance? Least number of edges in the symmetric difference of $G$ and some graph in BCC? – Louigi Addario-Berry Dec 3 '10 at 22:36
• Distance is edit distance. Disjoint is vertex disjoint. Sorry for not being clear. – 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)
• 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|$. – Jeremy H Dec 6 '10 at 22:15
• 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|$. – Aaron Meyerowitz Dec 7 '10 at 0:16