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* biclique^{1}?

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.