Ahlswede–Khachatrian theorem

Short description: Theorem in extremal set theory

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 [math]\displaystyle{ \{1,\dots,n\} }[/math] of size k, as well as the families achieving the maximum size.

Statement

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

[math]\displaystyle{ \mathcal{F}_{n,k,t,r} = \{ A \subseteq \{1,\dots,n\} : |A|=k \text{ and } |A \cap \{1,\dots,t+2r\}| \ge t+r \}. }[/math]

The Ahlswede–Khachatrian theorem states that if [math]\displaystyle{ \cal F }[/math] is t-intersecting then

[math]\displaystyle{ |\cal F| \leq \max_{r\colon t+2r \leq n} |\mathcal{F}_{n,k,t,r}|. }[/math]

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

More explicitly, if

[math]\displaystyle{ (k-t+1)(2+\tfrac{t-1}{r+1}) \lt n \lt (k-t+1)(2+\tfrac{t-1}{r}) }[/math]

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

[math]\displaystyle{ (k-t+1)(2+\tfrac{t-1}{r+1}) = n }[/math]

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

History

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

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

[math]\displaystyle{ |\{ A \subseteq \{1,\ldots,4m\} : |A|=2m \text{ and } |A \cap \{1,\ldots,2m\}| \ge m+1 \}|, }[/math]

which coincides with the size of the Frankl family [math]\displaystyle{ \mathcal{F}_{4m,2m,2,m-1} }[/math]. 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 [math]\displaystyle{ \{1,\dots,n\} }[/math]. When [math]\displaystyle{ {{{1}}} }[/math] is odd, the unique optimal family consists of all sets of size at least [math]\displaystyle{ m+1 }[/math] (corresponding to the Majority function), and when [math]\displaystyle{ {{{1}}} }[/math] is odd, the unique optimal families consist of all sets whose intersection with a fixed set of size [math]\displaystyle{ 2m-1 }[/math] is at least [math]\displaystyle{ m-1 }[/math] (Majority on [math]\displaystyle{ 2m-1 }[/math] 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 [math]\displaystyle{ \mu_p }[/math]-measure, where [math]\displaystyle{ \mu_p }[/math] is given by the formula

[math]\displaystyle{ \mu_p(S) = p^{|S|} (1-p)^{n-|S|}. }[/math]

The measure [math]\displaystyle{ \mu_p }[/math] corresponds to the process which chooses a random subset of [math]\displaystyle{ \{1,\dots,n\} }[/math] by adding each element with probability p independently.

Katona's intersection theorem is the case [math]\displaystyle{ {{{1}}} }[/math]. Friedgut considered the case [math]\displaystyle{ p\lt 1/2 }[/math]. The weighted analog of the Erdős–Ko–Rado theorem states that if [math]\displaystyle{ \cal F }[/math] is intersecting then [math]\displaystyle{ \mu_p(\cal F) \leq p }[/math] for all [math]\displaystyle{ p \lt 1/2 }[/math], with equality if and only if [math]\displaystyle{ \cal F }[/math] consists of all sets containing a fixed point. Friedgut proved the analog of Wilson's result in this setting: if [math]\displaystyle{ \cal F }[/math] is t-intersecting then [math]\displaystyle{ \mu_p(\cal F) \leq p^t }[/math] for all [math]\displaystyle{ p \lt 1/(t+1) }[/math], with equality if and only if [math]\displaystyle{ \cal F }[/math] 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 [math]\displaystyle{ p \lt 1/2 }[/math]. To state the weighted version, we first define the analogs of the Frankl families:

[math]\displaystyle{ \mathcal{F}_{n,t,r} = \{ A \subseteq \{1,\dots,n\} : |A \cap \{1,\dots,t+2r\}| \ge t+r \}. }[/math]

The weighted Ahlswede–Khachatrian theorem states that if [math]\displaystyle{ \cal F }[/math] is t-intersecting then for all [math]\displaystyle{ 0 \lt p \lt 1 }[/math],

[math]\displaystyle{ \mu_p(\mathcal{F}) \leq \max_{r\colon t+2r \leq n} \mu_p(\mathcal{F}_{n,t,r}), }[/math]

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

[math]\displaystyle{ \frac{r}{t+2r-1} \leq p \leq \frac{r+1}{t+2r+1}. }[/math]

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

Filmus weighted Ahlswede–Khachatrian theorem for all [math]\displaystyle{ n,t,p }[/math] using the original arguments of Ahlswede and Khachatrian for [math]\displaystyle{ p\lt 1/2 }[/math], and using a different argument of Ahlswede and Khachatrian, originally used to provide an alternative proof of Katona's theorem, for [math]\displaystyle{ p\ge1/2 }[/math].

Version for strings

Ahlswede and Khachatrian proved a version of the Ahlswede–Khachatrian theorem for strings over a finite alphabet. Given a finite alphabet [math]\displaystyle{ \Sigma }[/math], 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

[math]\displaystyle{ \mathcal{F}_{n,t,r} = \{ w \in \Sigma^n : |w \cap w_0| \ge t+r \}, }[/math]

where [math]\displaystyle{ w_0 \in \Sigma^n }[/math] is an arbitrary word, and [math]\displaystyle{ |w \cap w_0| }[/math] is the number of positions in which w and [math]\displaystyle{ w_0 }[/math] agree.

The Ahlswede–Khachatrian theorem for strings states that if [math]\displaystyle{ \cal F }[/math] is t-intersecting then

[math]\displaystyle{ |\mathcal{F}| \leq \max_{r\colon t+2r \leq n} |\mathcal{F}_{n,t,r}|, }[/math]

with equality if and only if [math]\displaystyle{ \cal F }[/math] is equivalent to a Frankl family.

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

References

Works cited

• Ahlswede, Rudolf; Khachatrian, Levon H. (1996). "The complete nontrivial-intersection theorem for systems of finite sets". Journal of Combinatorial Theory, Series A 76 (1): 121–138. doi:10.1006/jcta.1996.0092. 
• Ahlswede, Rudolf; Khachatrian, Levon H. (1997). "The complete intersection theorem for systems of finite sets". European Journal of Combinatorics 18 (2): 125–136. doi:10.1006/eujc.1995.0092. 
• Ahlswede, Rudolf; Khachatrian, Levon H. (1999). "A Pushing-Pulling Method: New Proofs of Intersection Theorems". Combinatorica 19: 1–15. doi:10.1007/s004930050042. 
• Ahlswede, Rudolf; Khachatrian, Levon H. (1998). "The Diametric Theorem in Hamming Spaces—Optimal Anticodes". Advances in Applied Mathematics 20 (4): 429–449. doi:10.1006/aama.1998.0588. 
• Ahlswede, Rudolf; Khachatrian, Levon H. (2004). "Katona's Intersection Theorem: Four Proofs". Combinatorica 25: 105–110. doi:10.1007/s00493-005-0008-4. 
• Deza, Michel; Frankl, Peter (1983). "Erdős–Ko–Rado theorem—22 years later". SIAM Journal on Algebraic Discrete Methods 4 (4): 419–431. doi:10.1137/0604042. 
• Dinur, Irit; Safra, Shmuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics 162 (1): 439–485. doi:10.4007/annals.2005.162.439. 
• Erdős, Paul (1987). "My joint work with Richard Rado". 123. pp. 53–80. 
• Erdős, Paul; Ko, Chao; Rado, Richard (1961). "Intersection theorems for systems of finite sets". Quarterly Journal of Mathematics. Second Series 12: 313–320. doi:10.1093/qmath/12.1.313. https://www.renyi.hu/~p_erdos/1961-07.pdf. 
• Filmus, Yuval (2017). "The weighted complete intersection theorem". Journal of Combinatorial Theory, Series A 151: 84–101. doi:10.1016/j.jcta.2017.04.008. 
• Fishburn, P. C.; Frankl, P.; Freed, D.; Lagarias, J. C.; Odlyzko, A. M. (1986). "Probabilities for Intersecting Systems and Random Subsets of Finite Sets". SIAM Journal on Algebraic Discrete Methods 7 (1): 73–79. doi:10.1137/0607009. 
• Frankl, Peter (1978). "The Erdős–Ko–Rado theorem is true for [math]\displaystyle{ n \ge ckt }[/math]". Coll. Soc. Maj. J. Bolyai 11: 365–375. 
• Friedgut, Ehud (2008). "On the measure of intersecting families, uniqueness and stability". Combinatorica 28 (5): 503–528. doi:10.1007/s00493-008-2318-9. 
• Katona, Gy. (1964). "Intersection theorems for systems of finite sets". Acta Mathematica Academiae Scientiarum Hungaricae 15 (3–4): 329–337. doi:10.1007/BF01897141. http://real.mtak.hu/21124/1/paper_1.pdf. 
• Wilson, Richard M. (1984). "The exact bound in the Erdős-Ko-Rado theorem". Combinatorica 4 (2–3): 247–257. doi:10.1007/BF02579226.