# Minimal size of the maximum 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 vertex on side $R$ is connected to $k$ vertices on side $L$, and that $|R| < k< |L|$.

I'm interested in the regime in which $k /|R| \rightarrow \infty$, $|L|/(|R|(|L|-k)) \rightarrow 0$ and $k/ |L| \rightarrow 1$ . Note that this implies that each vertex in $R$ is connected to almost all the vertices in $L$.

Question: What is the minimal size (i.e., number of edges) of the maximum biclique1?
The answer should depend on all constants: $|R|,|L|$ and $k$ .

Note that a greedy approach (adding vertices one by one in $R$) naively gives $|L|^2/(4(|L|-k))$. However, I'm looking for a better solution, if one exists.

1 Maximum biclique: The largest (in terms of number of edges) complete bipartite subgraph. Not to be confused with a maximal biclique.

• So what if you take the disjoint union of some stars, i.e., $K_{1,k}\cup \ldots\cup K_{1,k}$? The minimum size of a maximum biclique will be $k$ and this clearly can't be beaten. – domotorp Aug 10 '17 at 19:43
• The problem is that it is not possible for stars to be disjoint if $k$ is too large. For example if $|L|-1=k$. – Daniel Soudry Aug 11 '17 at 4:30
• So do you expect an answer as a function of not only $k$, but also of $|L|$ and $|R|$? – domotorp Aug 11 '17 at 11:26
• I doubt that we may in general get anything better than $k$ edges (achieved for a trivial biclique with 1 vertex in $R$ and $k$ vertices in $L$), only for $k$ close to $L$. Indeed, in order to beat this bound, you should have some $m$ vertices in $R$ having more than $k/m$ common neighbours in $L$. But If you choose $R$ subsets of neighbours at random, the probability of such event is small for reasonably large $L$. – Fedor Petrov Aug 12 '17 at 9:14
• If you believe the random intuition then you're looking to maximise $a(1-\delta)^a |L|$, with $k = (1-\delta)|L|$. A maximum of around $|L| / \delta e$ is achieved near $a = 1/\delta$, which is your greedy bound with $4$ replaced by $e$. – Ben Barber Aug 28 '17 at 10:56