# 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 $\{1,\dots ,n\}$ of size k, as well as the families achieving the maximum size.

## Statement

Let $n\geq k\geq t\geq 1$ be integer parameters. A t-intersecting family ⁠${\cal {F}}$⁠ is a collection of subsets of $\{1,\dots ,n\}$ of size k such that if ⁠$A,B\in {\cal {F}}$⁠ then $|A\cap B|\geq t$. Frankl constructed the t-intersecting families
    ${\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 ⁠${\cal {F}}$⁠ is t-intersecting then
    $|{\cal {F|\leq \max _{r\colon t+2r\leq n}|{\mathcal {F}}_{n,k,t,r}|.}}$
Furthermore, equality is possible only if ⁠${\cal {F}}$⁠ is equivalent to a Frankl family, meaning that it coincides with one after permuting the coordinates.
More explicitly, if
    $(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 $r=0$) then $|{\mathcal {F}}|\leq |{\mathcal {F}}_{n,k,t,r}|$, with equality if an only if ⁠${\cal {F}}$⁠ is equivalent to ${\mathcal {F}}_{n,k,t,r}$; and if
    $(k-t+1)(2+{\tfrac {t-1}{r+1}})=n$
then $|{\mathcal {F}}|\leq |{\mathcal {F}}_{n,k,t,r}|=|{\mathcal {F}}_{n,k,t,r+1}|$, with equality if an only if ⁠${\cal {F}}$⁠ is equivalent to ${\mathcal {F}}_{n,k,t,r}$ or to ${\mathcal {F}}_{n,k,t,r+1}$.

## History

Erdős, Ko and Rado showed that if $n\geq t+(k-t){\binom {k}{t}}^{2}$ then the maximum size of a t-intersecting family is $|{\mathcal {F}}_{n,k,t,0}|={\binom {n-t}{k-t}}$. Frankl proved that when $t\geq 15$, the same bound holds for all $n\geq (t+1)(k-t-1)$, which is tight due to the example ${\mathcal {F}}_{n,k,t,1}$. This was extended to all t (using completely different techniques) by Wilson.
As for smaller n, Erdős, Ko and Rado made the ⁠$4m$⁠ conjecture, which states that when $(n,k,t)=(4m,2m,2)$, the maximum size of a t-intersecting family is
    $|\{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 ${\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 and using its dual. 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.

## Related results
### Weighted version

Katona's intersection theorem determines the maximum size of an intersecting family of subsets of $\{1,\dots ,n\}$. When ⁠${1}$⁠ is odd, the unique optimal family consists of all sets of size at least ⁠$m+1$⁠ (corresponding to the Majority function), and when ⁠${1}$⁠ is odd, the unique optimal families consist of all sets whose intersection with a fixed set of size ⁠$2m-1$⁠ is at least ⁠$m-1$⁠ (Majority on ⁠$2m-1$⁠ coordinates).
Friedgut considered a measure-theoretic generalization of Katona's theorem, in which instead of maximizing the size of the intersecting family, we maximize its ⁠$\mu _{p}$⁠-measure, where ⁠$\mu _{p}$⁠ is given by the formula
    $\mu _{p}(S)=p^{|S|}(1-p)^{n-|S|}.$
The measure ⁠$\mu _{p}$⁠ corresponds to the process which chooses a random subset of $\{1,\dots ,n\}$ by adding each element with probability p independently.
Katona's intersection theorem is the case ⁠${1}$⁠. Friedgut considered the case ⁠$p<1/2$⁠. The weighted analog of the Erdős–Ko–Rado theorem states that if ⁠${\cal {F}}$⁠ is intersecting then ⁠$\mu _{p}({\cal {F)\leq p}}$⁠ for all ⁠$p<1/2$⁠, with equality if and only if ⁠${\cal {F}}$⁠ consists of all sets containing a fixed point. Friedgut proved the analog of Wilson's result in this setting: if ⁠${\cal {F}}$⁠ is t-intersecting then ⁠$\mu _{p}({\cal {F)\leq p^{t}}}$⁠ for all ⁠$p<1/(t+1)$⁠, with equality if and only if ⁠${\cal {F}}$⁠ consists of all sets containing t fixed points. Friedgut's techniques are similar to Wilson's.
Dinur and Safra and Ahlswede and Khachatrian observed that the Ahlswede–Khachatrian theorem implies its own weighted version, for all ⁠$p<1/2$⁠. To state the weighted version, we first define the analogs of the Frankl families:
    ${\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 ⁠${\cal {F}}$⁠ is t-intersecting then for all ⁠$0<p<1$⁠,
    $\mu _{p}({\mathcal {F}})\leq \max _{r\colon t+2r\leq n}\mu _{p}({\mathcal {F}}_{n,t,r}),$
with equality only if ⁠${\cal {F}}$⁠ is equivalent to a Frankl family. Explicitly, ${\mathcal {F}}_{n,t,r}$ is optimal in the range
    ${\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 ⁠$p<1/2$⁠, without the characterization of the optimal cases. The main idea is that if we take a random subset of $\{1,\dots ,N\}$ of size ⁠$\lfloor pN\rfloor$⁠, then the distribution of its intersection with $\{1,\ldots ,n\}$ tends to ⁠$\mu _{p}$⁠ as ⁠$N\to \infty$⁠.
Filmus proved weighted Ahlswede–Khachatrian theorem for all ⁠$n,t,p$⁠ using the original arguments of Ahlswede and Khachatrian for ⁠$p<1/2$⁠, and using a different argument of Ahlswede and Khachatrian, originally used to provide an alternative proof of Katona's theorem, for ⁠$p\geq 1/2$⁠. He also showed that the Frankl families are the unique optimal families for all ⁠$n,t,p$⁠.

### Version for strings

Ahlswede and Khachatrian proved a version of the Ahlswede–Khachatrian theorem for strings over a finite alphabet. Given a finite alphabet ⁠$\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
    ${\mathcal {F}}_{n,t,r}=\{w\in \Sigma ^{n}:|w\cap w_{0}|\geq t+r\},$
where ⁠$w_{0}\in \Sigma ^{n}$⁠ is an arbitrary word, and $|w\cap w_{0}|$ is the number of positions in which w and ⁠$w_{0}$⁠ agree.
The Ahlswede–Khachatrian theorem for strings states that if ⁠${\cal {F}}$⁠ is t-intersecting then
    $|{\mathcal {F}}|\leq \max _{r\colon t+2r\leq n}|{\mathcal {F}}_{n,t,r}|,$
with equality if and only if ⁠${\cal {F}}$⁠ is equivalent to a Frankl family.
The theorem is proved by a reduction to the weighted Ahlswede–Khachatrian theorem, with $p=1/|\Sigma |$.