# Minimal size of the maximal biclique

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.

• 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 – Peter Heinig Aug 9 '17 at 14:45
• 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. – Daniel Soudry Aug 9 '17 at 15:11
• @DanielSoudry I expect that by $|R| \ll k$ you mean that $R$ is "much smaller than $k$". Is that right? – Dan Cranston Aug 9 '17 at 21:27
• Yes, clarified (I guess I am still thinking about inequalities in my native right-to-left language). – 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.)
• 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! – Daniel Soudry Aug 10 '17 at 8:39
• @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. – Dan Cranston Aug 10 '17 at 14:10
• 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 – Daniel Soudry Aug 11 '17 at 4:22