During my semester in Budapest, I took Combinatorics 2, which the syllabus labeled as Combinatorics on Set Systems, but which in reality was a course on hypergraph theory. The course was taught by a sweet man named András Gyárfás, whom I later learned was one of the most frequent collaborators of Paul Erdős. It seemed to me like one of those classes that not many people take (even though they easily could), yet it contains some of the most influential and essential pieces of mathematics.
I aim to provide a brief introduction of this topic here and hope to build to the Erdős–Ko–Rado Theorem.
Brief Introduction
In graph theory, we have a set of vertices and a set of edges with each edge “connecting” two vertices. Formally, we say that a graph $G=(V,E)$, where $V$ is a set of vertices and $E \subseteq \binom{V}{2}$ is a set of edges. In graph theory, edges only involve two vertices.
A hypergraph is a basic generalization of graphs. Each edge can “connect” any number of vertices. Formally, a hypergraph $H=(V,E)$ where $V$ is a set of vertices and $E \subseteq \mathcal{P}(V)$. Drawing hypergraphs quickly becomes extremely difficult, so it’s worth thinking of them as “set systems” instead of visualizable graphs (hence the name “Combinatorics on Set Systems”).
We say a hypergraph is $k$-uniform if every edge is connected to $k$ vertices. In other words, $E \subseteq \binom{V}{k}$. Here, this can also be thought of as collections of $k$-element subsets. This also allows us to characterize graphs as just $2$-uniform hypergraphs. A canonical example of a $3$-uniform hypergraph is the Fano plane.
We can then define a family $\mathcal{F} \subseteq \binom{[n]}{k}$ is intersecting if:
\[A \cap B \neq \emptyset \quad \text{for all } A,B \in \mathcal{F}\]Note that $[n]$ denotes the set $ \{ 1,2,\dots,n-1,n \} $.
If you imagine a graph where vertices represent $k$ sized sets and edges represent “disjointness”, then this intersecting idea represents independent sets. If edges represent disjointness, then an “independent set” (vertices that share no edges) implies that no two sets are disjoint, which means that they all intersect. This is often called a Kneser Graph.
Now, fix an element $i \in [n]$. If we let $\mathcal{F}_i = \{ A \in \binom{[n]}{k} : i \in A \}$, then we have that every pair here intersects, and $ | \mathcal{F}_i | = \binom{n-1}{k-1}$. This is called a star.
It turns out, this is the largest possible size, and this is precisely the Erdős–Ko–Rado Theorem (1961).
Erdős–Ko–Rado Theorem (1961)
The theorem states: If $n \geq 2k$, then any intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ satisfies
\[| \mathcal{F} | \leq \binom{n-1}{k-1}\]Moreover, if $n > 2k$, equality holds only for stars.
Note that we need $n \geq 2k$ because if $n < 2k$, any two sets of size $k$ must intersect by Pigeonhole Principle, meaning the entire set of $\binom{[n]}{k}$ is intersecting.
The intuition behind the theorem is that if a family is not “anchored” by a single element (like a star), the sets are forced to “spread out” across the domain. This spreading increases the likelihood of disjointedness, preventing the family from reaching that maximum size.
In the future, I may include a full proof, but I hope that this brief introduction was sufficient in showcasing the complexity and overall vibe of hypergraph theory. Moving from graphs ($k=2$) to hypergraphs ($k \ge 3$) causes the difficulty in studying these structures to explode, but it allows us to come up with so many fascinating results. To me, generalizing edges in this way was like opening up Pandora’s box.