Block Design

For any power $ p$ of a prime number and any natural number $ n\le p$ there exist at least $ p^{n}$ subsets of $ \{1,\ldots,p^2\}$ for which each pair has less than $ n$ elements in common.

\includegraphics[width=0.8\linewidth]{BlockDesignFig.eps}

The figure illustrates the case $ p=n=3$ with the pixels of each column corresponding to a subset.

In general, the number of subsets is asymptotically optimal, as is evident from the upper bound $ \binom{p^2}{n} / \binom{p}{n} = p^n + O(p^{n-1})$, $ p\to\infty$.


$ \square$ Lemma 2,Dissertation, Bonn, 1979

[previous] [next]