Definition 1.1.1.
Given a set \(X\) and integer \(k\text{,}\) define
\begin{equation*}
\binom{X}{k}:=\{A\subseteq X: |A|=k\}\text{.}
\end{equation*}
We refer to \(\binom{X}{k}\) as the \(k\)th level of \(2^{X}\text{.}\)
Section 1.1 Intersecting Families
A family \(\mathcal{F}\) of sets is intersecting if \(A\cap B\neq\emptyset\) for all \(A,B\in \mathcal{F}\text{.}\) It is not hard to determine the size of the largest intersecting family in \(2^{[n]}\text{.}\) The problem, however, becomes more interesting if we restrict to families of sets of the same cardinality. Consider the following definition.
Remark 1.1.3.
A pair \((V,E)\) where \(V\) is a set and \(E\subseteq \binom{V}{k}\) is often referred to as a (\(k\)-uniform) hypergraph . In this part of the notes, while discussing extremal set theory, we will speak mainly in the language of “set systems.” The word “hypergraphs” will be used later in the notes when focusing on problems originating in graph theory. However, one should be aware that there is no material difference between a set system in \(\binom{[n]}{k}\) and a \(k\)-uniform hypergraph with vertex set \([n]\text{.}\)
As you are probably aware, the number of subsets of \([n]\) of cardinality \(k\) is equal to the \(k\)th binomial coefficient; i.e.,
\begin{equation*}
\left|\binom{[n]}{k}\right|=\binom{n}{k} = \frac{n!}{k!(n-k)!}\text{.}
\end{equation*}
Our focus in this section is on the following question:
Question 1.1.4.
What is the maximum cardinality of an intersecting family \(\mathcal{F}\subseteq \binom{[n]}{k}\text{?}\)
Let us analyze a few examples.
Example 1.1.5.
If \(k>n/2\text{,}\) then any two sets in \(\binom{[n]}{k}\) have non-empty intersection by the Pigeonhole Principle, and so the answer to Question 1.1.4 in this case is simply \(\binom{n}{k}\text{.}\)
Question 1.1.4 becomes more interesting when \(k\leq n/2\text{.}\)
Example 1.1.6.
Suppose that \(k\leq n/2\) and define
\begin{equation*}
\mathcal{F}:=\{A\subseteq [n]: 1\in A\}\text{.}
\end{equation*}
Clearly, \(\mathcal{F}\) is intersecting. Thus, there exists an intersecting family of cardinality \(\binom{n-1}{k-1}\text{.}\)
Example 1.1.7.
Suppose that \(n=2k\) and let \(\mathcal{F}\subseteq \binom{n}{k}\) be any collection such that \(\mathcal{F}\) contains exactly one of \(A\) or \([n]\setminus A\) for every \(A\in \binom{[n]}{k}\) (note that both of these sets have size \(k\text{,}\) since \(n=2k\)). Then it is not hard to see that \(\mathcal{F}\) is intersecting and satisfies
\begin{equation*}
|\mathcal{F}| = \frac{1}{2}\binom{n}{k} = \frac{1}{2}\binom{2k}{k} = \binom{2k-1}{k-1} = \binom{n-1}{k-1}\text{.}
\end{equation*}
(the equality \(\frac{1}{2}\binom{2k}{k} = \binom{2k-1}{k-1}\) is by Pascal’s Formula and the fact that \(\binom{a}{b}=\binom{a}{b-a}\)). Thus, this is an alternative construction giving the same bound as Example 1.1.6 (but only in the special case \(n=2k\)).
As it turns out, the constructions in Examples 1.1.6 and Example 1.1.7 are optimal.
Theorem 1.1.9. Erdős–Ko–Rado Theorem [97].
If \(n\) and \(k\) are integers such that \(n\geq2k\text{,}\) then every intersecting family \(\mathcal{F}\subseteq \binom{[n]}{k}\) satisfies \(|\mathcal{F}|\leq \binom{n-1}{k-1}\text{.}\)
Proof.
Let \(\mathbb{Z}_n\) denote the integers modulo \(n\text{;}\) that is, \(\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}\text{.}\) An interval in \(\mathbb{Z}_n\) is a set of the form \(\{i,i+1,\dots,i+t\}\) for \(0\leq i,t\leq n-1\text{,}\) where addition is viewed modulo \(n\text{.}\)
Let \(f:[n]\to \mathbb{Z}_n\) be a random bijection. For any set \(A\subseteq [n]\) and an interval \(I\) in \(\mathbb{Z}_n\text{,}\) each of cardinality exactly \(k\text{,}\) the probability that \(f(A)=I\) is precisely
\begin{equation*}
\frac{k!(n-k)!}{n!} = \frac{1}{\binom{n}{k}}\text{.}
\end{equation*}
There are exactly \(n\) intervals of length \(k\) in \(\mathbb{Z}_n\text{.}\) Thus, by linearity of expectation, the expected number of sets \(A\in \mathcal{F}\) mapped to an interval under \(f\) is
1
See Appendix B.
\begin{equation*}
\sum_{A\in\mathcal{F}}\left(\sum_{I\text{ an interval in } \mathbb{Z}_n} \mathbb{P}(f(A)=I)\right) = \frac{|\mathcal{F}|\cdot n}{\binom{n}{k}}\text{.}
\end{equation*}
Next, let us prove that no bijection \(f:[n]\to\mathbb{Z}_n\) can map more than \(k\) sets of \(\mathcal{F}\) to intervals. Here is the reason. Suppose that \(A\in \mathcal{F}\) such that \(f(A)\) is the interval \(\{i,i+1,\dots,i+k-1\}\text{.}\) If \(B\) is another set of \(\mathcal{F}\text{,}\) then, since \(A\cap B\neq\emptyset\text{,}\) we have \(f(A)\cap f(B)\neq \emptyset\text{.}\) If \(f(B)\) is an interval, then \(f(B)\) must start at one of the points \(i+1,\dots,i+k-1\) or end at one of the points \(i,\dots,i+k-2\text{;}\) note that it cannot start at \(i\) or end at \(i+k-1\) because \(A\neq B\text{.}\) Moreover, since \(n\geq 2k\text{,}\) the interval \(f(B)\) cannot both start and end in \(f(A)\text{.}\) Therefore, each set \(B\in\mathcal{F}\) with \(B\neq A\) which is mapped to an interval “cuts” the set \(A\) into two intervals (the elements of \(B\cap A\) and \(A\setminus B\)). No two different sets \(B\in\mathcal{F}\) can cut \(A\) in the same way, as this would imply that those two sets are either the same or are disjoint (again, we are using \(n\geq 2k\)). Thus, there are at most \(k-1\) sets in \(\mathcal{F}\) apart from \(A\) which map to an interval; so, there is a total of at most \(k\) such sets overall.
Putting this all together,
\begin{equation*}
\frac{|\mathcal{F}|\cdot n}{\binom{n}{k}}\leq k
\end{equation*}
which implies that
\begin{equation*}
|\mathcal{F}|\leq \binom{n-1}{k-1}
\end{equation*}
and we are done.
Later, in Section 2.3, we will see a second proof of the Erdős–Ko–Rado Theorem using the powerful Kruskal–Katona Theorem.
Here are a couple of YouTube videos related to the Erdős–Ko–Rado Theorem:
