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 [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[1] 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[2] 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[3] 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.[4]
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[5][6]
- [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[7] and using its dual.[8] 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.[9]
Related results
Weighted version
Katona's intersection theorem[10] 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[11] 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[12] 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[13] 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[14] and Ahlswede and Khachatrian[15] 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[16] weighted Ahlswede–Khachatrian theorem for all [math]\displaystyle{ n,t,p }[/math] using the original arguments of Ahlswede and Khachatrian[17][18] 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].[19]
Version for strings
Ahlswede and Khachatrian proved a version of the Ahlswede–Khachatrian theorem for strings over a finite alphabet.[20] 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
Notes
- ↑ (Frankl 1978)
- ↑ (Erdős Ko)
- ↑ (Frankl 1978)
- ↑ (Wilson 1984)
- ↑ (Erdős 1987)
- ↑ (Deza Frankl)
- ↑ (Ahlswede Khachatrian)
- ↑ (Ahlswede Khachatrian)
- ↑ (Ahlswede Khachatrian)
- ↑ (Katona 1964)
- ↑ (Friedgut 2008)
- ↑ (Fishburn Frankl)
- ↑ (Wilson 1984)
- ↑ (Dinur Safra)
- ↑ (Ahlswede Khachatrian)
- ↑ (Filmus 2017)
- ↑ (Ahlswede Khachatrian)
- ↑ (Ahlswede Khachatrian)
- ↑ (Ahlswede Khachatrian)
- ↑ (Ahlswede Khachatrian)
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.
Original source: https://en.wikipedia.org/wiki/Ahlswede–Khachatrian theorem.
Read more |