Q:

Covering a complete graph with as few complete bipartite subgraphs as possible

The biclique covering number $bc(G)$ of a graph $G$ is the smallest number of bicliques (complete bipartite subgraphs) of $G$ such that every edge of $G$ belongs to at least one of these bicliques.
Quoted from the paper "On covering graphs by complete bipartite subgraphs" by S. Jukna and A.S. Kulikov, 2009:

We have $bc(K_n) \le \lceil \log_2 n \rceil$: just encode the
  vertices of $K_n$ (complete graph with $n$ vertices) by binary vectors of length $m = \lceil \log_2 n \rceil$ and define, for each $i = 1, \ldots, m$, a biclique containing all edges, the
  codes of whose endpoints differ in the $i$th coordinate.

For example, to cover $K_6$, we write 
\begin{align}
  1 = 001 \\
  2 = 010 \\
  3 = 011 \\
  4 = 100 \\
  5 = 101 \\
  6 = 110
\end{align}
The three bicliques are thus $K_{\{1,2,3\}, \{4,5,6\}}, K_{\{1,4,5\}, \{2,3,6\}}, \text{ and } K_{\{1,3,5\}, \{2,4,6\}}$, corresponding to the leftmost, the middle, and the rightmost bits, respectively.
Note that the result above is $bc(K_n) \color{red}{\le} \lceil \log_2 n \rceil$. My question is what is the exact value of $bc(K_n)$ and how to prove it? In other words, what is the smallest number of bicliques to cover $K_n$? 

A:

This is tight: we have $bc(K_n) = \left\lceil \log_2 n\right\rceil$. This proof of the lower bound can be found in Fishburn and Hammer's Bipartite dimensions and bipartite degrees of graphs.
We prove that $bc(K_n) \ge \log_2 n$ by strong induction on $n$. To cover $K_n$, suppose that $K_{p,q}$ is the first biclique we put down. We may assume $p+q=n$, since if we didn't include a vertex at all, we could add it to either side of the biclique and only increase the set of edges covered.
The vertices on either side of the first biclique induce a $K_p$ and a $K_q$ respectively that we haven't touched at all yet. Since $p+q=n$, either $p \ge \frac n2$ or $q \ge \frac n2$, so we have a clique of size at least $\frac n2$ left to cover. By the inductive hypothesis, this needs at least $\log_2 \frac n2 = (\log_2 n) -1$ more bicliques. 
Together with the first biclique we put down, that brings us to a total of $\log_2 n$ bicliques needed to cover $K_n$, which proves the result by induction on $n$.

