Ahlswede–Khachatrian theorem

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

Statement

Let $n\ge k\ge t\ge 1$ be integer parameters. A Template:Mvar-intersecting family Template:Tmath is a collection of subsets of $\{1,\dots ,n\}$ of size Template:Mvar such that if Template:Tmath then $|A\cap B|\ge t$. Frankl constructed the Template:Mvar-intersecting families

${ℱ}_{n,k,t,r}=\{A\subseteq \{1,\dots ,n\}:|A|=k\text{ and }|A\cap \{1,\dots ,t+2r\}|\ge t+r\}.$

The Ahlswede–Khachatrian theorem states that if Template:Tmath is Template:Mvar-intersecting then

$|ℱ\mathcal{|}\mathcal{\le }\underset{𝓇\mathcal{:}𝓉\mathcal{+}2𝓇\mathcal{\le }𝓃}{\mathcal{max}}\mathcal{|}{ℱ}_{𝓃,𝓀,𝓉,𝓇}\mathcal{|}\mathcal{.}$

Furthermore, equality is possible only if Template:Tmath is equivalent to a Frankl family, meaning that it coincides with one after permuting the coordinates.

More explicitly, if

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

(where the upper bound is ignored when $r=0$) then $|ℱ|\le |{ℱ}_{n,k,t,r}|$, with equality if an only if Template:Tmath is equivalent to ${ℱ}_{n,k,t,r}$; and if

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

then $|ℱ|\le |{ℱ}_{n,k,t,r}|=|{ℱ}_{n,k,t,r+1}|$, with equality if an only if Template:Tmath is equivalent to ${ℱ}_{n,k,t,r}$ or to ${ℱ}_{n,k,t,r+1}$.

History

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

As for smaller Template:Mvar, Erdős, Ko and Rado made the Template:Tmath conjecture, which states that when $(n,k,t)=(4m,2m,2)$, the maximum size of a Template:Mvar-intersecting family is

$|\{A\subseteq \{1,\dots ,4m\}:|A|=2m\text{ and }|A\cap \{1,\dots ,2m\}|\ge m+1\}|,$

which coincides with the size of the Frankl family ${ℱ}_{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 Template:Mvar-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 Template:Tmath is odd, the unique optimal family consists of all sets of size at least Template:Tmath (corresponding to the Majority function), and when Template:Tmath is odd, the unique optimal families consist of all sets whose intersection with a fixed set of size Template:Tmath is at least Template:Tmath (Majority on Template:Tmath 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 Template:Tmath-measure, where Template:Tmath is given by the formula

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

The measure Template:Tmath corresponds to the process which chooses a random subset of $\{1,\dots ,n\}$ by adding each element with probability Template:Mvar independently.

Katona's intersection theorem is the case Template:Tmath. Friedgut considered the case Template:Tmath. The weighted analog of the Erdős–Ko–Rado theorem states that if Template:Tmath is intersecting then Template:Tmath for all Template:Tmath, with equality if and only if Template:Tmath consists of all sets containing a fixed point. Friedgut proved the analog of Wilson's result in this setting: if Template:Tmath is Template:Mvar-intersecting then Template:Tmath for all Template:Tmath, with equality if and only if Template:Tmath consists of all sets containing Template:Mvar 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 Template:Tmath. To state the weighted version, we first define the analogs of the Frankl families:

${ℱ}_{n,t,r}=\{A\subseteq \{1,\dots ,n\}:|A\cap \{1,\dots ,t+2r\}|\ge t+r\}.$

The weighted Ahlswede–Khachatrian theorem states that if Template:Tmath is Template:Mvar-intersecting then for all Template:Tmath,

${\mu }_p(ℱ)\le \underset{r:t+2r\le n}{\max }{\mu }_p({ℱ}_{n,t,r}),$

with equality only if Template:Tmath is equivalent to a Frankl family. Explicitly, ${ℱ}_{n,t,r}$ is optimal in the range

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

The argument of Dinur and Safra proves this result for all Template:Tmath, without the characterization of the optimal cases. The main idea is that if we take a random subset of $\{1,\dots ,N\}$ of size Template:Tmath, then the distribution of its intersection with $\{1,\dots ,n\}$ tends to Template:Tmath as Template:Tmath.

Filmus proved weighted Ahlswede–Khachatrian theorem for all Template:Tmath using the original arguments of Ahlswede and Khachatrian for Template:Tmath, and using a different argument of Ahlswede and Khachatrian, originally used to provide an alternative proof of Katona's theorem, for Template:Tmath. He also showed that the Frankl families are the unique optimal families for all Template:Tmath.

Version for strings

Ahlswede and Khachatrian proved a version of the Ahlswede–Khachatrian theorem for strings over a finite alphabet. Given a finite alphabet Template:Tmath, a collection of strings of length Template:Mvar is Template:Mvar-intersecting if any two strings in the collection agree in at least Template:Mvar places. The analogs of the Frankl family in this setting are

${ℱ}_{n,t,r}=\{w\in {\mathrm{\Sigma }}^n:|w\cap w_0|\ge t+r\},$

where Template:Tmath is an arbitrary word, and $|w\cap w_0|$ is the number of positions in which Template:Mvar and Template:Tmath agree.

The Ahlswede–Khachatrian theorem for strings states that if Template:Tmath is Template:Mvar-intersecting then

$|ℱ|\le \underset{r:t+2r\le n}{\max }|{ℱ}_{n,t,r}|,$

with equality if and only if Template:Tmath is equivalent to a Frankl family.

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

References

Works cited

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite conference
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal