Partitioning the edges of the complete graph into complete bipartite graphs

Michiel Smid

Let V={1,2,...,n} be a set of size n and consider the complete graph K_n on V. Let A_i, B_i, i=1,2,...,k, be a sequence of subsets of V such that

for all i: A_i and B_i are disjoint,
for any pair p,q in V, there is exactly one i such that p in A_i and q in B_i.

What can we say about:

the smallest possible value of k?
the smallest possible value of sum_i (|A_i|+|B_i|) ?

It turns out that the answers to these questions have been known for more than 40 years. I will present simple (and very clever) proofs of the following results:

k is at least n-1. (The proof is due to Tverberg, 1982.)
sum_i (|A_i|+|B_i|) = Omega(n log n). (The proof is due to Bollobas and Scott, 2007.)

These results have the following implications:

In any WSPD, there are at least n-1 pairs. Of course, this was known already, but this proof does not use any metric properties.
Mohammad's SSPD is optimal.