In extremal set theory, the Ahlswede–Khachatrian theorem generalizes the Erdős–Ko–Rado theorem to -intersecting families. Given parameters, and, it describes the maximum size of a -intersecting family of subsets of
\{1,...,n\}
Let
n\gek\get\ge1
\{1,...,n\}
|A\capB|\get
l{F}n,k,t,r=\{A\subseteq\{1,...,n\}:|A|=kand|A\cap\{1,...,t+2r\}|\get+r\}.
The Ahlswede–Khachatrian theorem states that if is -intersecting then
|\calF|\leqmaxr\colon|l{F}n,k,t,r|.
Furthermore, equality is possible only if 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
|l{F}|\leq|l{F}n,k,t,r|
l{F}n,k,t,r
(k-t+1)(2+\tfrac{t-1}{r+1})=n
then
|l{F}|\leq|l{F}n,k,t,r|=|l{F}n,k,t,r+1|
l{F}n,k,t,r
l{F}n,k,t,r+1
Erdős, Ko and Rado showed that if
n\get+(k-t)\binom{k}{t}2
|l{F}n,k,t,0|=\binom{n-t}{k-t}
t\ge15
n\ge(t+1)(k-t-1)
l{F}n,k,t,1
As for smaller, Erdős, Ko and Rado made the conjecture, which states that when
(n,k,t)=(4m,2m,2)
|\{A\subseteq\{1,\ldots,4m\}:|A|=2mand|A\cap\{1,\ldots,2m\}|\gem+1\}|,
l{F}4m,2m,2,m-1
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 -intersecting family with the additional condition that no element is contained in all sets of the family.
Katona's intersection theorem determines the maximum size of an intersecting family of subsets of
\{1,...,n\}
Friedgut considered a measure-theoretic generalization of Katona's theorem, in which instead of maximizing the size of the intersecting family, we maximize its -measure, where is given by the formula
\mup(S)=p|S|(1-p)n-|S|.
The measure corresponds to the process which chooses a random subset of
\{1,...,n\}
Katona's intersection theorem is the case . Friedgut considered the case . The weighted analog of the Erdős–Ko–Rado theorem states that if is intersecting then for all, with equality if and only if consists of all sets containing a fixed point. Friedgut proved the analog of Wilson's result in this setting: if is -intersecting then for all, with equality if and only if consists of all sets containing 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 . To state the weighted version, we first define the analogs of the Frankl families:
l{F}n,t,r=\{A\subseteq\{1,...,n\}:|A\cap\{1,...,t+2r\}|\get+r\}.
The weighted Ahlswede–Khachatrian theorem states that if is -intersecting then for all,
\mup(l{F})\leqmaxr\colon\mup(l{F}n,t,r),
with equality only if is equivalent to a Frankl family. Explicitly,
l{F}n,t,r
| r | |
| t+2r-1 |
\leqp\leq
| r+1 | |
| t+2r+1 |
.
The argument of Dinur and Safra proves this result for all, without the characterization of the optimal cases. The main idea is that if we take a random subset of
\{1,...,N\}
\{1,\ldots,n\}
Filmus proved weighted Ahlswede–Khachatrian theorem for all using the original arguments of Ahlswede and Khachatrian for, and using a different argument of Ahlswede and Khachatrian, originally used to provide an alternative proof of Katona's theorem, for . He also showed that the Frankl families are the unique optimal families for all .
Ahlswede and Khachatrian proved a version of the Ahlswede–Khachatrian theorem for strings over a finite alphabet. Given a finite alphabet, a collection of strings of length is -intersecting if any two strings in the collection agree in at least places. The analogs of the Frankl family in this setting are
l{F}n,t,r=\{w\in\Sigman:|w\capw0|\get+r\},
|w\capw0|
The Ahlswede–Khachatrian theorem for strings states that if is -intersecting then
|l{F}|\leqmaxr\colon|l{F}n,t,r|,
with equality if and only if is equivalent to a Frankl family.
The theorem is proved by a reduction to the weighted Ahlswede–Khachatrian theorem, with
p=1/|\Sigma|