Skip to main content

Section 1.5 Partitioning into Intersecting Families

We conclude this chapter with a beautiful application of topological ideas to a problem involving intersecting families. Specifically, our goal will be to determine, for \(n\geq2k\text{,}\) the minimum number \(m\) such that \(\binom{[n]}{k}\) can be partitioned into \(m\) intersecting families. We start with a natural construction based on the tight constructions for the Erdős–Ko–Rado Theorem.
described in detail following the image
“Sphere.”

Example 1.5.1.

For \(1\leq i\leq n-2k+1\text{,}\) let
\begin{equation*} \mathcal{F}_i:=\left\{A\in \binom{[n]}{k}: i=\min(A)\right\}\text{.} \end{equation*}
Then, clearly, every set in \(\mathcal{F}_i\) contains \(i\) and so \(\mathcal{F}_i\) is intersecting. Also, every set in the family \(\mathcal{F}_0:=\binom{[n]}{k}\setminus\bigcup_{i=1}^{n-2k+1}\mathcal{F}_i\) is contained within \(\{n-2k+2,\dots,n\}\text{,}\) which has cardinality \(2k-1\text{.}\) By the Pigeonhole Principle, any two subsets of cardinality \(k\) from a set of size \(2k-1\) must intersect, and therefore \(\mathcal{F}_0\) is intersecting as well. Therefore, \(\binom{[n]}{k}\) can be partitioned into \(n-2k+2\) intersecting families.
Our focus in this section is on proving the following theorem, which asserts that this construction is best possible. It was first conjectured by Kneser [174] and proved in a groundbreaking paper of Lovász [200].
We will present a slightly simpler proof of Theorem 1.5.2, using similar ideas to the original proof, due to Greene [140]. The proof relies on a topological theorem which is equivalent to the Borsuk–Ulam Theorem. We will discuss these topological results further at the end of the section; for now, we just use apply them to prove Theorem 1.5.2. Let \(\|\cdot\|_2\) denote the standard Euclidean norm.

Definition 1.5.3.

For \(d\geq0\text{,}\) let \(\mathbb{S}_d\) be the unit sphere in \(\mathbb{R}^{d+1}\text{;}\) i.e.
\begin{equation*} \mathbb{S}_{d}:=\{x\in \mathbb{R}^{d+1}: \|x\|_2=1\}\text{.} \end{equation*}

Definition 1.5.4.

A set \(U\subseteq \mathbb{S}_{d}\) is said to be open if it can be formed from open hemispheres by finite intersections and countable unions. It is closed if its complement is open.
In other words, in any covering of \(\mathbb{S}_d\) by \(d+1\) sets such that \(d\) of the sets are open or closed, there must be a set of the covering which contains a pair of antipodal points. We now use Theorem 1.5.5 to derive Theorem 1.5.2.

Proof of Theorem 1.5.2.

Let \(d=n-2k+1\) and suppose, to the contrary, that there is a partition of \(\binom{[n]}{k}\) into intersecting families \(\mathcal{F}_1,\dots,\mathcal{F}_{d}\text{.}\)
Let \(x_1,\dots,x_n\) be uniformly random points in \(\mathbb{S}_d\) chosen independently of one another. For each \(x\in\mathbb{S}_d\text{,}\) define \(H(x)\) to be the open hemisphere centred at \(x\text{.}\) For each \(A\in \binom{[n]}{k}\text{,}\) define
\begin{equation*} H(A) := \bigcap_{j\in F}H(x_j)\text{.} \end{equation*}
The set \(H(A)\) is open since it is the intersection of finitely many open sets. Also, for each \(1\leq i\leq d\text{,}\) define
\begin{equation*} U_i:=\bigcup_{A\in \mathcal{F}_i}H(A)\text{.} \end{equation*}
Then \(U_i\) is open as well. Define \(U_0:=\mathbb{S}_d\setminus\bigcup_{i=1}^{d}U_i\text{.}\) Then the sets \(U_0,U_1,\dots,U_d\) cover \(\mathbb{S}_d\text{.}\) By Theorem 1.5.5, there exists an index \(i\) and \(x\in \mathbb{S}_d\) such that \(\{x,-x\}\subseteq U_i\text{.}\) We divide the proof into cases.

Case.

\(i=0\text{.}\)
Consider the set \(T:=\{j\in [n]: x_j\in H(x)\}\text{.}\) We claim that \(|T|\leq k-1\text{.}\) If not, then let \(A\) be a subset of \(T\) of cardinality \(k\text{.}\) Note that, for any two points \(y,z\) in the sphere, we have \(z\in H(y)\) if and only if \(y\in H(z)\text{.}\) So, since \(x_j\in H(x)\) for all \(j\in A\text{,}\) we must have that \(x\in H(A)\text{.}\) Since \(\mathcal{F}_1,\dots,\mathcal{F}_d\) partition \(\binom{[n]}{k}\text{,}\) there must be some \(i\in [d]\) such that \(A\in\mathcal{F}_i\text{.}\) But then \(x\in U_i\) which contradicts the fact that \(x\in U_0\text{.}\)
Therefore, \(|T|\leq k-1\text{.}\) Analogously, the set \(T':=\{j\in [n]: x_j\in H(-x)\}\) also has cardinality at most \(k-1\text{.}\) Thus, among the points \(x_1,\dots,x_n\text{,}\) there are at least \(n-2k+2 = d+1\) points that are in \(\mathbb{S}_d\setminus (H(x)\cup H(-x))\text{.}\) In other words, there are at least \(d+1\) such points that are contained in the plane \(\{z: \langle z,x\rangle=0\}\subseteq \mathbb{R}^{d+1}\text{.}\) However, \(x_1,\dots,x_n\) were chosen at random, and so the probability that any plane contains more than \(d\) of them is zero. So, with probability \(1\text{,}\) the set \(U_0\) cannot contain two antipodal points \(x\) and \(-x\text{.}\)

Case.

\(1\leq i\leq d\text{.}\)
Since \(x\in U_i\text{,}\) there must exist \(A\in \mathcal{F}_i\) such that \(x\in H(A)\text{.}\) This implies that \(x_j\in H(x)\) for all \(j\in A\text{.}\) Similarly, there exists \(A'\in \mathcal{F}_i\) such that \(x_j\in H(-x)\) for all \(j\in A'\text{.}\) Since the hemispheres \(H(x)\) and \(H(-x)\) are disjoint, we have that \(\{x_j: j\in A\}\cap \{x_j: j\in A'\}=\emptyset\text{.}\) However, this implies that \(A\cap A'=\emptyset\text{,}\) which contradicts the assumption that \(\mathcal{F}_i\) is intersecting and completes the proof!
Let us come back to provide a bit of context for the topological ideas that we are applying. Theorem 1.5.5 can be seen to be a consequence of the following well-known statement, known as the Borsuk–Ulam Theorem.
We will not prove the Borsuk–Ulam Theorem as it is beyond the scope of these notes, but we show that it implies Theorem 1.5.5.

Proof of Theorem 1.5.5.

For a point \(x\in \mathbb{S}_d\) and subset \(U\subseteq \mathbb{S}_d\text{,}\) define \(\mu(x,U):=\inf_{y\in U}\|x-y\|_2\text{.}\) Define \(f:\mathbb{S}_d\to \mathbb{R}^d\) by
\begin{equation*} f(x) = (\mu(x,U_1),\mu(x,U_2),\dots,\mu(x,U_d))\text{.} \end{equation*}
Then \(f\) is continuous and so, by Theorem 1.5.6, there must exist a point \(x\in \mathbb{S}_d\) such that \(f(x)=f(-x)\text{.}\)
If \(\{x,-x\}\subseteq U_0\text{,}\) then we are done; so we can assume, without loss of generality, that \(x\notin U_0\text{.}\) So, without loss of generality, \(x\in U_1\text{.}\) Since \(x\in U_1\text{,}\) we have that \(\mu(x,U_1)=0\text{.}\) However, since \(f(x)=f(-x)\text{,}\) this implies that \(\mu(-x,U_1)=0\) as well. This means that \(-x\) is in the closure of \(U_1\text{.}\) If \(U_1\) is closed, then this would give us that \(-x\in U_1\) and we would be done (as we already know that \(x\in U_1\)). So, we assume that \(U_1\) is open. Since \(U_1\) is open, we can let \(B\) be an open ball around \(x\) that is contained within \(U_1\) and let \(B' = \{-y: y\in B\}\text{.}\) Then \(B'\) is an open ball around \(-x\text{.}\) Since \(-x\) is in the closure of \(U_1\text{,}\) we can take \(z\in B'\cap U_1\text{.}\) The point \(-z\) is in \(B\) which is a subset of \(U_1\) by construction. So, \(\{z,-z\}\subseteq U_1\) and we are done.
Here is a YouTube video related to Kneser’s Conjecture: