Homework 5 (pdf version)
Dense distributions vs flat distributions
Do Exercise 19.7. You may assume the hyperplane separation theorem.
Min Max theorem from hyperplane separation
Do Exercise 19.6. You may assume the hyperplane separation theorem.
Limitations of combinatorial designs
Show the following limitation on combinatorial designs: If \(S_1,\ldots,S_k\) are subsets of a universe \(U\) such that for some \(\rho > 0\), \(|S_i| = \rho|U|\) and \(|S_i\cap S_j| \le \rho^2 |U|/2\) for every distinct \(i, j\in [k]\) then \(k \le \lceil 2/\rho\rceil\).
Hint: Represent the sets \(S_1,\ldots,S_k\) as \(|U|\)-dimensional real-valued vectors such that the inner products between the vectors are a simple function of the intersection sizes of the sets.