|
1
|
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$? |
|||||||||
|
|
3
|
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) |
||||||||
|
