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.

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

- 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.)

- 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.