Английская Википедия:Ahlswede–Khachatrian theorem

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description In extremal set theory, the Ahlswede–Khachatrian theorem generalizes the Erdős–Ko–Rado theorem to Шаблон:Mvar-intersecting families. Given parameters Шаблон:Mvar, Шаблон:Mvar and Шаблон:Mvar, it describes the maximum size of a Шаблон:Mvar-intersecting family of subsets of <math>\{1,\dots,n\}</math> of size Шаблон:Mvar, as well as the families achieving the maximum size.

Statement

Let <math>n \ge k \ge t \ge 1</math> be integer parameters. A Шаблон:Mvar-intersecting family Шаблон:Tmath is a collection of subsets of <math>\{1,\dots,n\}</math> of size Шаблон:Mvar such that if Шаблон:Tmath then <math>|A\cap B| \ge t</math>. Frankl[1] constructed the Шаблон:Mvar-intersecting families

<math>

\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 Шаблон:Tmath is Шаблон:Mvar-intersecting then

<math>

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

Furthermore, equality is possible only if Шаблон:Tmath is equivalent to a Frankl family, meaning that it coincides with one after permuting the coordinates.

More explicitly, if

<math>

(k-t+1)(2+\tfrac{t-1}{r+1}) < n < (k-t+1)(2+\tfrac{t-1}{r}) </math>

(where the upper bound is ignored when <math>r=0</math>) then <math>|\mathcal{F}| \leq |\mathcal{F}_{n,k,t,r}|</math>, with equality if an only if Шаблон:Tmath is equivalent to <math>\mathcal{F}_{n,k,t,r}</math>; and if

<math>

(k-t+1)(2+\tfrac{t-1}{r+1}) = n </math>

then <math>|\mathcal{F}| \leq |\mathcal{F}_{n,k,t,r}| = |\mathcal{F}_{n,k,t,r+1}|</math>, with equality if an only if Шаблон:Tmath is equivalent to <math>\mathcal{F}_{n,k,t,r}</math> or to <math>\mathcal{F}_{n,k,t,r+1}</math>.

History

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

As for smaller Шаблон:Mvar, Erdős, Ko and Rado made the Шаблон:Tmath conjecture, which states that when <math>(n,k,t)=(4m,2m,2)</math>, the maximum size of a Шаблон:Mvar-intersecting family is[5][6]

<math>

|\{ 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>\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 Шаблон:Mvar-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>\{1,\dots,n\}</math>. When Шаблон:Tmath is odd, the unique optimal family consists of all sets of size at least Шаблон:Tmath (corresponding to the Majority function), and when Шаблон:Tmath is odd, the unique optimal families consist of all sets whose intersection with a fixed set of size Шаблон:Tmath is at least Шаблон:Tmath (Majority on Шаблон:Tmath 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 Шаблон:Tmath-measure, where Шаблон:Tmath is given by the formula

<math>

\mu_p(S) = p^{|S|} (1-p)^{n-|S|}. </math>

The measure Шаблон:Tmath corresponds to the process which chooses a random subset of <math>\{1,\dots,n\}</math> by adding each element with probability Шаблон:Mvar independently.

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

<math>

\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 Шаблон:Tmath is Шаблон:Mvar-intersecting then for all Шаблон:Tmath,

<math>

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

with equality only if Шаблон:Tmath is equivalent to a Frankl family. Explicitly, <math>\mathcal{F}_{n,t,r}</math> is optimal in the range

<math>

\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 Шаблон:Tmath, without the characterization of the optimal cases. The main idea is that if we take a random subset of <math>\{1,\dots,N\}</math> of size Шаблон:Tmath, then the distribution of its intersection with <math>\{1,\ldots,n\}</math> tends to Шаблон:Tmath as Шаблон:Tmath.

Filmus[16] weighted Ahlswede–Khachatrian theorem for all Шаблон:Tmath using the original arguments of Ahlswede and Khachatrian[17][18] for Шаблон:Tmath, and using a different argument of Ahlswede and Khachatrian, originally used to provide an alternative proof of Katona's theorem, for Шаблон:Tmath.[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 Шаблон:Tmath, a collection of strings of length Шаблон:Mvar is Шаблон:Mvar-intersecting if any two strings in the collection agree in at least Шаблон:Mvar places. The analogs of the Frankl family in this setting are

<math>

\mathcal{F}_{n,t,r} = \{ w \in \Sigma^n : |w \cap w_0| \ge t+r \}, </math> where Шаблон:Tmath is an arbitrary word, and <math>|w \cap w_0|</math> is the number of positions in which Шаблон:Mvar and Шаблон:Tmath agree.

The Ahlswede–Khachatrian theorem for strings states that if Шаблон:Tmath is Шаблон:Mvar-intersecting then

<math>

|\mathcal{F}| \leq \max_{r\colon t+2r \leq n} |\mathcal{F}_{n,t,r}|, </math>

with equality if and only if Шаблон:Tmath is equivalent to a Frankl family.

The theorem is proved by a reduction to the weighted Ahlswede–Khachatrian theorem, with <math>p=1/|\Sigma|</math>.

References

Notes

Шаблон:Reflist

Works cited

Шаблон:Refbegin

Шаблон:Refend

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvtxt
  2. ↑ Шаблон:Harvtxt
  3. ↑ Шаблон:Harvtxt
  4. ↑ Шаблон:Harvtxt
  5. ↑ Шаблон:Harvtxt
  6. ↑ Шаблон:Harvtxt
  7. ↑ Шаблон:Harvtxt
  8. ↑ Шаблон:Harvtxt
  9. ↑ Шаблон:Harvtxt
  10. ↑ Шаблон:Harvtxt
  11. ↑ Шаблон:Harvtxt
  12. ↑ Шаблон:Harvtxt
  13. ↑ Шаблон:Harvtxt
  14. ↑ Шаблон:Harvtxt
  15. ↑ Шаблон:Harvtxt
  16. ↑ Шаблон:Harvtxt
  17. ↑ Шаблон:Harvtxt
  18. ↑ Шаблон:Harvtxt
  19. ↑ Шаблон:Harvtxt
  20. ↑ Шаблон:Harvtxt
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Ahlswede–Khachatrian_theorem&oldid=12982668