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

What can we say about:
  1. the smallest possible value of k?
  2. 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:
  1. k is at least n-1. (The proof is due to Tverberg, 1982.)
  2. 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:
  1. 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.
  2. Mohammad's SSPD is optimal.