Ahlswede–Khachatrian theorem

In extremal set theory, the Ahlswede–Khachatrian theorem generalizes the Erdős–Ko–Rado theorem to t-intersecting families. Given parameters n, k and t, it describes the maximum size of a t-intersecting family of subsets of ${\displaystyle \{1,\dots ,n\}}$ of size k, as well as the families achieving the maximum size.

Let ${\displaystyle n\geq k\geq t\geq 1}$ be integer parameters. A t-intersecting family ⁠${\displaystyle {\cal {F}}}$⁠ is a collection of subsets of ${\displaystyle \{1,\dots ,n\}}$ of size k such that if ⁠${\displaystyle A,B\in {\cal {F}}}$⁠ then ${\displaystyle |A\cap B|\geq t}$. Frankl^[1] constructed the t-intersecting families

${\displaystyle {\mathcal {F}}_{n,k,t,r}=\{A\subseteq \{1,\dots ,n\}:|A|=k{\text{ and }}|A\cap \{1,\dots ,t+2r\}|\geq t+r\}.}$

The Ahlswede–Khachatrian theorem states that if ⁠${\displaystyle {\cal {F}}}$⁠ is t-intersecting then

${\displaystyle |{\cal {F|\leq \max _{r\colon t+2r\leq n}|{\mathcal {F}}_{n,k,t,r}|.}}}$

Furthermore, equality is possible only if ⁠${\displaystyle {\cal {F}}}$⁠ is equivalent to a Frankl family, meaning that it coincides with one after permuting the coordinates.

More explicitly, if

${\displaystyle (k-t+1)(2+{\tfrac {t-1}{r+1}})<n<(k-t+1)(2+{\tfrac {t-1}{r}})}$

(where the upper bound is ignored when ${\displaystyle r=0}$) then ${\displaystyle |{\mathcal {F}}|\leq |{\mathcal {F}}_{n,k,t,r}|}$, with equality if an only if ⁠${\displaystyle {\cal {F}}}$⁠ is equivalent to ${\displaystyle {\mathcal {F}}_{n,k,t,r}}$; and if

${\displaystyle (k-t+1)(2+{\tfrac {t-1}{r+1}})=n}$

then ${\displaystyle |{\mathcal {F}}|\leq |{\mathcal {F}}_{n,k,t,r}|=|{\mathcal {F}}_{n,k,t,r+1}|}$, with equality if an only if ⁠${\displaystyle {\cal {F}}}$⁠ is equivalent to ${\displaystyle {\mathcal {F}}_{n,k,t,r}}$ or to ${\displaystyle {\mathcal {F}}_{n,k,t,r+1}}$.

Erdős, Ko and Rado^[2] showed that if ${\displaystyle n\geq t+(k-t){\binom {k}{t}}^{2}}$ then the maximum size of a t-intersecting family is ${\displaystyle |{\mathcal {F}}_{n,k,t,0}|={\binom {n-t}{k-t}}}$. Frankl^[1] proved that when ${\displaystyle t\geq 15}$, the same bound holds for all ${\displaystyle n\geq (t+1)(k-t-1)}$, which is tight due to the example ${\displaystyle {\mathcal {F}}_{n,k,t,1}}$. This was extended to all t (using completely different techniques) by Wilson.^[3]

As for smaller n, Erdős, Ko and Rado made the ⁠${\displaystyle 4m}$⁠ conjecture, which states that when ${\displaystyle (n,k,t)=(4m,2m,2)}$, the maximum size of a t-intersecting family is^[4][5]

${\displaystyle |\{A\subseteq \{1,\ldots ,4m\}:|A|=2m{\text{ and }}|A\cap \{1,\ldots ,2m\}|\geq m+1\}|,}$

which coincides with the size of the Frankl family ${\displaystyle {\mathcal {F}}_{4m,2m,2,m-1}}$. This conjecture is a special case of the Ahlswede–Khachatrian theorem.

Ahlswede and Khachatrian proved their theorem in two different ways: using generating sets^[6] and using its dual.^[7] Using similar techniques, they later proved the corresponding Hilton–Milner theorem, which determines the maximum size of a t-intersecting family with the additional condition that no element is contained in all sets of the family.^[8]

Katona's intersection theorem^[9] determines the maximum size of an intersecting family of subsets of ${\displaystyle \{1,\dots ,n\}}$. When ⁠${\displaystyle {1}}$⁠ is odd, the unique optimal family consists of all sets of size at least ⁠${\displaystyle m+1}$⁠ (corresponding to the Majority function), and when ⁠${\displaystyle {1}}$⁠ is odd, the unique optimal families consist of all sets whose intersection with a fixed set of size ⁠${\displaystyle 2m-1}$⁠ is at least ⁠${\displaystyle m-1}$⁠ (Majority on ⁠${\displaystyle 2m-1}$⁠ coordinates).

Friedgut^[10] considered a measure-theoretic generalization of Katona's theorem, in which instead of maximizing the size of the intersecting family, we maximize its ⁠${\displaystyle \mu _{p}}$⁠-measure, where ⁠${\displaystyle \mu _{p}}$⁠ is given by the formula

${\displaystyle \mu _{p}(S)=p^{|S|}(1-p)^{n-|S|}.}$

The measure ⁠${\displaystyle \mu _{p}}$⁠ corresponds to the process which chooses a random subset of ${\displaystyle \{1,\dots ,n\}}$ by adding each element with probability p independently.

Katona's intersection theorem is the case ⁠${\displaystyle {1}}$⁠. Friedgut considered the case ⁠${\displaystyle p<1/2}$⁠. The weighted analog of the Erdős–Ko–Rado theorem^[11] states that if ⁠${\displaystyle {\cal {F}}}$⁠ is intersecting then ⁠${\displaystyle \mu _{p}({\cal {F)\leq p}}}$⁠ for all ⁠${\displaystyle p<1/2}$⁠, with equality if and only if ⁠${\displaystyle {\cal {F}}}$⁠ consists of all sets containing a fixed point. Friedgut proved the analog of Wilson's result^[3] in this setting: if ⁠${\displaystyle {\cal {F}}}$⁠ is t-intersecting then ⁠${\displaystyle \mu _{p}({\cal {F)\leq p^{t}}}}$⁠ for all ⁠${\displaystyle p<1/(t+1)}$⁠, with equality if and only if ⁠${\displaystyle {\cal {F}}}$⁠ consists of all sets containing t fixed points. Friedgut's techniques are similar to Wilson's.

Dinur and Safra^[12] and Ahlswede and Khachatrian^[13] observed that the Ahlswede–Khachatrian theorem implies its own weighted version, for all ⁠${\displaystyle p<1/2}$⁠. To state the weighted version, we first define the analogs of the Frankl families:

${\displaystyle {\mathcal {F}}_{n,t,r}=\{A\subseteq \{1,\dots ,n\}:|A\cap \{1,\dots ,t+2r\}|\geq t+r\}.}$

The weighted Ahlswede–Khachatrian theorem states that if ⁠${\displaystyle {\cal {F}}}$⁠ is t-intersecting then for all ⁠${\displaystyle 0<p<1}$⁠,

${\displaystyle \mu _{p}({\mathcal {F}})\leq \max _{r\colon t+2r\leq n}\mu _{p}({\mathcal {F}}_{n,t,r}),}$

with equality only if ⁠${\displaystyle {\cal {F}}}$⁠ is equivalent to a Frankl family. Explicitly, ${\displaystyle {\mathcal {F}}_{n,t,r}}$ is optimal in the range

${\displaystyle {\frac {r}{t+2r-1}}\leq p\leq {\frac {r+1}{t+2r+1}}.}$

The argument of Dinur and Safra proves this result for all ⁠${\displaystyle p<1/2}$⁠, without the characterization of the optimal cases. The main idea is that if we take a random subset of ${\displaystyle \{1,\dots ,N\}}$ of size ⁠${\displaystyle \lfloor pN\rfloor }$⁠, then the distribution of its intersection with ${\displaystyle \{1,\ldots ,n\}}$ tends to ⁠${\displaystyle \mu _{p}}$⁠ as ⁠${\displaystyle N\to \infty }$⁠.

Filmus^[14] proved weighted Ahlswede–Khachatrian theorem for all ⁠${\displaystyle n,t,p}$⁠ using the original arguments of Ahlswede and Khachatrian^[6][7] for ⁠${\displaystyle p<1/2}$⁠, and using a different argument of Ahlswede and Khachatrian, originally used to provide an alternative proof of Katona's theorem, for ⁠${\displaystyle p\geq 1/2}$⁠.^[15] He also showed that the Frankl families are the unique optimal families for all ⁠${\displaystyle n,t,p}$⁠.

Ahlswede and Khachatrian proved a version of the Ahlswede–Khachatrian theorem for strings over a finite alphabet.^[13] Given a finite alphabet ⁠${\displaystyle \Sigma }$⁠, a collection of strings of length n is t-intersecting if any two strings in the collection agree in at least t places. The analogs of the Frankl family in this setting are

${\displaystyle {\mathcal {F}}_{n,t,r}=\{w\in \Sigma ^{n}:|w\cap w_{0}|\geq t+r\},}$

where ⁠${\displaystyle w_{0}\in \Sigma ^{n}}$⁠ is an arbitrary word, and ${\displaystyle |w\cap w_{0}|}$ is the number of positions in which w and ⁠${\displaystyle w_{0}}$⁠ agree.

The Ahlswede–Khachatrian theorem for strings states that if ⁠${\displaystyle {\cal {F}}}$⁠ is t-intersecting then

${\displaystyle |{\mathcal {F}}|\leq \max _{r\colon t+2r\leq n}|{\mathcal {F}}_{n,t,r}|,}$

with equality if and only if ⁠${\displaystyle {\cal {F}}}$⁠ is equivalent to a Frankl family.

The theorem is proved by a reduction to the weighted Ahlswede–Khachatrian theorem, with ${\displaystyle p=1/|\Sigma |}$.