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.