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