We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, that $|R| < k< |L|$, and that $k$ is much larger than $|R|$.

What is the minimal size (i.e., number of edges) of the maximal biclique1?

1maximal biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.

  • $\begingroup$ would you please state what $\ll$ is supposed to mean here? Also: I, and I think, many others, would prefer the capital letter $K$ be replaced with $k$. (The latter is 'mere' tradition of course, i.e. to try to have notation and capitalization reflect the types of objects.) @ Daniel Soudry $\endgroup$ – Peter Heinig Aug 9 '17 at 14:45
  • $\begingroup$ Sure, I've edited the question to modify and clarify notation like you asked. in other words "$\ll$" is just an inequality in which one side is much larger than the other side. $\endgroup$ – Daniel Soudry Aug 9 '17 at 15:11
  • $\begingroup$ @DanielSoudry I expect that by $|R| \ll k$ you mean that $R$ is "much smaller than $k$". Is that right? $\endgroup$ – Dan Cranston Aug 9 '17 at 21:27
  • $\begingroup$ Yes, clarified (I guess I am still thinking about inequalities in my native right-to-left language). $\endgroup$ – Daniel Soudry Aug 10 '17 at 5:04

It seems the answer is 2. Start with a disjoint union of stars, each with the center in $R$ and $k$ leaves in $L$. Now pick two of those stars and identify a single leaf in each. You get a copy of $K_{2,1}$ that is a maximal biclique. (It is certainly not maximum, but that is not what was asked.)

  • $\begingroup$ Sorry, I don't follow: 1) What is $K_{2,1}$ and what did you mean by "copy"? 2) Why is this a biclique (i.e., complete biparatite subgraph)? Thanks! $\endgroup$ – Daniel Soudry Aug 10 '17 at 8:39
  • $\begingroup$ @DanielSoudry In general $K_{a,b}$ means a bipartite graph with $a$ vertices on one side, $b$ vertices on the other side, and all possible edges between the two sides. So $K_{2,1}$ is simply a path on 3 vertices. By "copy of $K_{2,1}$" I mean that $K_{2,1}$ appears as a subgraph. From the definition of $K_{2,1}$ now it should be clear that this is a biclique. It is maximal because those two centers with a common neighbor have no other common neighbors and their common neighbor has no other neighbors at all. $\endgroup$ – Dan Cranston Aug 10 '17 at 14:10
  • $\begingroup$ Oh, I see it wasn't clear to me that "identify" means that both stars have only one common leaf. I see your point now. I'll open another question on "maximum", and give you the answer... Thanks! $\endgroup$ – Daniel Soudry Aug 10 '17 at 17:00
  • $\begingroup$ Wait, but this is not true if there is too much unavoidable overlap. For example, if $|R|=2, k=5, |L|=6$ then the minimal maximal bicluque has size $2×4=8$. @Dan Cranston $\endgroup$ – Daniel Soudry Aug 11 '17 at 4:22

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.