Section 16.2 Extremal Set Theory
Let \(n\) be a positive integer and let \([n]=1,2,\dots,n\text{.}\) In this section, we consider problems having the following general form: What is the maximum size of a family of subsets of \([n]\) when the family is required to satisfy certain properties.
Here is an elementary example.
Example 16.6.
The maximum size of a family \(\cgF\) of subsets of \([n]\text{,}\) with \(A\cap B\neq\emptyset\) for all \(A,B\in\cgF\text{,}\) is \(2^{n-1}\text{.}\)
For the lower bound, consider the family \(\cgF\) of all subsets of \([n]\) that contain \(1\text{.}\) Clearly this family has \(2^{n-1}\) elements and any two sets in the family have non-empty intersection.
For the upper bound, let \(\cgF\) be a family of subsets with each pair of sets in \(\cgF\) having non-empty intersection. Then whenever a subset \(S\) is a member of \(\cgF\text{,}\) the complement \(S'\) of \(S\) cannot belong to \(\cgF\text{.}\) Since the entire family of all \(2^n\) subsets of \([n]\) can be considered as \(2^{n-1}\) complementary pairs, and at most one set from each pair can belong to \(\cgF\text{,}\) we conclude that \(|\cgF|\le 2^{n-1}\text{.}\)
Example 16.7.
The maximum size of a family \(\cgF\) of subsets of \([n]\) subject to the constraint that when \(A\) and \(B\) are distinct sets in \(\cgF\text{,}\) then neither is a subset of the other, is \(\binom{n}{\lfloor n/2\rfloor}\text{.}\)
It is worth noting that in
Example 16.7, there is a very small number (one or two) of extremal families, i.e., when
\(\cgF\) is a family of subsets of
\([n]\text{,}\) \(|\cgF|= \binom{n}{\lfloor n/2\rfloor}\text{,}\) and no set in
\(\cgF\) is a proper subset of another, then either
\(\cgF=\{S\subseteq[n]: |S|=\lfloor n/2\rfloor\}\) or
\(\cgF=\{S\subseteq[n]: |S|=\lceil n/2\rceil\}\text{.}\) And of course, when
\(n\) is even, these are exactly the same family.
On the other hand, for
Example 16.6, there are many extremal families, since for every complementary pair of sets, either member can be selected.
We close this brief tasting of extremal set theory with a real classic.
Theorem 16.8. Erdős, Ko, Rado.
Let \(n\) and \(k\) be positive integers with \(n\ge 2k\text{.}\) Then the maximum size of a family \(\cgF\) of subsets of \([n]\) subject to the restrictions that (1) \(A\cap B\neq\emptyset\) for all \(A,B\in\cgF\text{,}\) and (2) \(|A|=k\) for all \(A\in\cgF\text{,}\) is \(\binom{n-1}{k-1}\text{.}\)
Proof.
For the lower bound, consider the family \(\cgF\) of all \(k\) element subset of \([n]\) that contain \(1\text{.}\)
For the upper bound, let \(\cgF\) be a family of subsets of \([n]\) satisfying the two constraints. We show that \(|\cgF|\le\binom{n-1}{k-1}\text{.}\) To accomplish this, we consider a circle in the Euclidean plane with \(n\) points \(p_1\text{,}\) \(p_2,\dots,p_n\) equally spaced points around its circumference. Then there are \(n!\) different ways (one for each permutation \(\sigma\) of \([n]\)) to place the integers in \([n]\) at the points in \(\{p_1,p_2,\dots,p_n\}\) in one to one manner.
For each permutation \(\sigma\) of \([n]\text{,}\) let \(\cgF(\sigma)\) denote the subfamily of \(\cgF\) consisting of all sets \(S\) from \(\cgF\) whose elements occur in a consecutive block around the circle. Then let \(t=\sum_\sigma|\cgF(\sigma)|\text{.}\)
Our first claim is that \(t\le kn!\text{.}\) To prove this, let \(\sigma\) be a permutation and suppose that \(|\cgF(\sigma)|=s \ge 1\text{.}\) Then the union of the sets from \(\cgF(\sigma)\) is a set of points that form a consecutive block of points on the circle. Note that since \(n\ge 2k\text{,}\) this block does not encompass the entire circle. Accordingly there is a set \(S\) whose elements are the first \(k\) in a clockwise sense within this block. Since each other set in \(\cgF\) represents a clockwise shift of one of more positions, it follows immediately that \(|\cgF|\le k\text{.}\) Since there are \(n!\) permutations, the claim follows.
We now claim that for each set \(S\in\cgF\text{,}\) there are exactly \(n k!(n-k)!\) permutations \(\sigma\) for which \(S\in\cgF(\sigma)\text{.}\) Note that there are \(n\) positions around the circle and each can be used as the first point in a block of \(k\) consecutive positions in which the elements of \(S\) can be placed. Then there are \(k!\) ways to order the elements of \(S\) and \((n-k)!\) ways to order the remaining elements. This proves our claim.
To complete the proof of the theorem, we note that we have
\begin{equation*}
|\cgF| n k! (n-k)!\le t\le k n!,
\end{equation*}
and this implies that \(|\cgF|le\binom{n-1}{k-1}\text{.}\)
