Доклады Российской академии наук. Математика, информатика, процессы управления, 2021, T. 499, № 1, стр. 17-19

ВВЕДЕНИЕ И ФОРМУЛИРОВКА РЕЗУЛЬТАТА

В данном сообщении речь пойдет о вероятностной версии классической задачи экстремальной комбинаторики, изучение которой было инициировано более полувека назад П. Эрдешем, Ч. Ко и Р. Радо. В своей работе упомянутые авторы доказали следующую замечательную теорему.

Теорема 1 (П. Эрдеш, Ч. Ко, Р. Радо). Пусть даны натуральные числа $r$ и s, $s < r$. Пусть ${{\mathcal{R}}_{n}} = {\text{\{ }}1,2, \ldots ,n{\text{\} }}$ – множество из $n$ элементов. Обозначим $m(n,r,s)$ максимальную мощность такой совокупности $r$-элементных подмножеств множества ${{\mathcal{R}}_{n}}$, что любые два подмножества в этой совокупности имеют не менее s общих элементов (такая совокупность называется s-пересекающейся). Тогда найдется такое ${{n}_{0}}(r,s)$, что при всех $n \geqslant {{n}_{0}}(r,s)$ выполнено $m(n,r,s) = C_{{n - s}}^{{r - s}}$.

Отметим, что оценка $m(n,r,s) \geqslant C_{{n - s}}^{{r - s}}$ практически очевидна: достаточно зафиксировать какие-либо s элементов ${{{v}}_{1}},{{{v}}_{2}}, \ldots ,{{{v}}_{s}} \in {{\mathcal{R}}_{n}}$ и рассмотреть все $r$-элементные подмножества, которые их содержат. В мировой литературе такую “тривиальную” s-пересекающуюся конструкцию принято называть звездой.

Ввиду своей исключительной значимости, результат теоремы 1 неоднократно обобщался и уточнялся. В частности, был получен ряд утверждений о своеобразной устойчивости результата Эрдеша–Ко–Радо. Ярким примером является, в первую очередь, так называемая граница Франкла, представленная последним в следующей формулировке.

Теорема 2 (П. Франкл). Пусть даны натуральные числа $r$ и s, $s < r$. Пусть $\mathcal{M}$ – произвольная s-пересекающаяся совокупность $r$-элементных подмножеств множества ${{\mathcal{R}}_{n}}$. Тогда найдется такое ${{n}_{0}}(r,s)$, что при всех $n{{n}_{0}}(r,s)$ либо $\mathcal{M}$ – это часть некоторой звезды, либо мощность $\mathcal{M}$ не превосходит величины

Важно сказать, что наименьшее ${{n}_{0}}(r,s)$ было определено Франклом и Уилсоном для любых r, s:

О современном состоянии исследований в области см. [1]. Мы же перейдем к версии устойчивости, которая изучалась в серии недавних работ (см. [2–9]).

Рассмотрим граф $G(n,r, < s) = (V(n,r)$, E(n, r, s)):

Напомним, что числом независимости $\alpha (G)$ графа $G$ называют размер максимального множества его вершин, попарно не соединенных ребрами (сами такие множества называются независимыми). Очевидно, что $\alpha (G(n,r, < s)) = m(n,r,s)$, а любая s-пересекающаяся совокупность $r$-элементных множеств взаимно однозначно отвечает некоторому независимому множеству вершин графа $G(n,r, < s)$. Графы такого типа активно изучаются в теории кодирования, в теории Рамсея, в теории гиперграфов, в комбинаторной геометрии (см. [10–24 ] ).

Теперь введем понятие случайного подграфа графа $G(n,r, < s)$. Пусть $p \in [0,\;1]$. Тогда ${{G}_{p}}(n,r, < s)$ – это случайный элемент со значениями во множестве всех остовных подграфов $G = (V(n,r),E)$ графа $G(n,r, < s)$ и с биномиальным распределением:

В работе [2] была доказана следующая теорема об устойчивости.

Теорема 3 (М.М. Пядеркин, А.М. Райгородский). Для любых фиксированных $r$ и $s$

Нам удалось доказать аналогичное утверждение для неконстантных параметров $r = r(n)$ и $s = s(n)$.

Теорема 4. Утверждение теоремы 3 верно для $r = r(n) \to \infty$, $s = s(n) \to \infty$ при условии, что

Отметим, что в доказательстве теоремы 4 очень существенно используется теорема 2, в которой присутствует неулучшаемое условие $(r - s + 1)(s + 1)$ < n. В частности, это условие означает, что ${{r}^{2}} < n$. Таким образом, ограничение вида ${{r}^{3}} < xn$, которое имеется по сути в теореме 4, вряд ли в рамках текущего метода удастся значительно ослабить. Иными словами, с точки зрения условий, теорема достаточно близка к оптимуму.

Также нам удалось перенести результат теоремы 3 на случай различных вероятностей ребра.

Теорема 5. Справедливы следующие две асимптотики.

1. Для любых констант $r$ и $s$ таких, что $r > s$ и $r > 3$, при вероятности сохранения ребра

2. Для любого $\varepsilon > 0$ и для любых констант r и s таких, что $r > s$, при вероятности сохранения ребра

При текущих ограничениях на $r$ и $s$ (нет зависимости от n) результат теоремы 5 практически неулучшаем.