1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 499, № 1, 2021

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

АСИМПТОТИКА ЧИСЛА НЕЗАВИСИМОСТИ СЛУЧАЙНОГО ПОДГРАФА ГРАФА G(n, r, < s)

В. С. Карась 1, П. А. Огарок 2, А. М. Райгородский 1, 2, 3, 4, *

1 Московский государственный университет имени М.В. Ломоносова
Москва, Россия

2 Московский физико-технический институт (национальный исследовательский университет)
Долгопрудный, Московская обл., Россия

3 Кавказский математический центр Адыгейского государственного университета
Майкоп, Республика Адыгея

4 Бурятский государственный университет, Институт математики и информатики
Улан-Удэ, Россия

* E-mail: mraigor@yandex.ru

Поступила в редакцию 26.03.2020
После доработки 15.05.2021
Принята к публикации 16.05.2021

Полный текст (PDF)

Аннотация

Рассматривается вопрос о вероятностной версии классической проблемы экстремальной комбинаторики. Представлены обобщения на случай непостоянных параметров и на случай различных вероятностей ребра для теоремы устойчивости, утверждающей, что число независимости случайного подграфа графа $G(n,r, < s)$ асимптотически не изменяется при независимом удалении ребер.

Ключевые слова: асимптотика, число независимости, случайный подграф, граф $G(n,r, < s)$

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

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

Теорема 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}$ не превосходит величины

$\begin{gathered} a)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(s + 2)C_{{n - s - 2}}^{{r - s - 1}} + C_{{n - s - 2}}^{{r - s - 2}} = \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = \;\left| {{\text{\{ }}V{\text{:}}\;\left| V \right| = r,\left| {{\text{\{ }}1,\; \ldots ,\;s + 2{\text{\} }} \cap V} \right| \geqslant s + 1{\text{\} }}} \right| \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,при\quad r \leqslant 2s + 1, \\ \end{gathered} $

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

${{n}_{0}}(r,s) = (r - s + 1)(s + 1).$

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

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

$\begin{gathered} V(n,r) = \left\{ {A \subset {\text{\{ }}1,\;2,\; \ldots ,\;n{\text{\} :}}\;\left| A \right| = r} \right\}, \\ E(n,r,s) = {\text{\{ \{ }}A,B{\text{\} :}}\;\left| {A \cap B} \right| < s{\text{\} }}. \\ \end{gathered} $

Напомним, что числом независимости $\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)$ и с биномиальным распределением:

$\mathbb{P}\left( {{{G}_{p}}(n,r, < s) = G} \right) = {{p}^{{|E|}}}{{(1 - p)}^{{|E(n,r,s)| - |E|}}}.$

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

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

$\mathbb{P}(\alpha \left( {{{G}_{{1/2}}}(n,r, < s)} \right) = C_{{n - s}}^{{r - s}}) \to 1,\quad n \to \infty .$

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

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

$r = o\left( {\mathop {\left( {\frac{n}{{lnn}}} \right)}\nolimits^{\frac{1}{3}} } \right),\quad s = o(r).$

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

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

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

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

$p \geqslant {{p}_{1}}(n) = \frac{{2sC_{r}^{s}lnn}}{{C_{{n - s}}^{{r - s}}}}$
имеем

$\mathbb{P}(\alpha \left( {{{G}_{p}}(n,r, < s)} \right) = C_{{n - s}}^{{r - s}}) \to 1,\quad n \to \infty .$

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

$p \leqslant {{p}_{2}}(n) = \frac{{(1 - \varepsilon )(r + s)lnn}}{{C_{{n - s}}^{{r - s}}}}$
имеем

$\mathbb{P}(\alpha \left( {{{G}_{p}}(n,r, < s)} \right)C_{{n - s}}^{{r - s}} + 1) \to 1,\quad n \to \infty .$

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

Список литературы

  1. Kupavskii A. Degree versions of theorems on intersecting families via stability // J. Comb. Theory Ser. A. 2019. V. 168. P. 272–287.

  2. Pyaderkin M.M. On the chromatic number of random subgraphs of a certain distance graph // Discrete Applied Mathematics. 2019. V. 267. P. 209–214.

  3. Пядёркин М.М. О пороговой вероятности для устойчивости независимых множеств в дистанционном графе // Матем. Заметки. 2019. Т. 106. № 2. С. 280–294.

  4. Деревянко Н.М., Киселев С.Г. Числа независимости случайных подграфов некоторого дистанционного графа // Пробл. передачи информ. 2017. Т. 53. № 4. С. 3–15.

  5. Пядёркин М.М. Числа независимости случайных подграфов дистанционных графов // Матеем. заметки. 2016. Т. 99. № 4. С. 564–573.

  6. Пядёркин М.М. Числа независимости случайных подграфов некоторого дистанционного графа // Матем. заметки. 2016. Т. 99. № 2. С. 288–297.

  7. Devlin Pat, Kahn Jeff. On “stability” in the Erdös–Ko–Rado Theorem // SIAM J. Discrete Math. 2016. V. 30. № 2. P. 1283–1289.

  8. Das Shagnik, Tran Tuan. Removal and Stability for Erdös–Ko–Rado Theorem // SIAM J. Discrete Math. 2016. V. 30. Iss. 2.

  9. Kupavskii A. On random subgraphs of Kneser and Schrijver graphs // J. Combinatorial Theory Ser. A. 2016. V. 30. Iss. 2.

  10. Kiselev S., Supavskii A. Rainbow matchings in k-partite hypergraphs // Bulletin of the London Mathematical Society. 2021. V. 53. № 2. P. 360–369.

  11. Купавский А.Б., Сагдеев А.А. Теория Рамсея в пространстве с чебышёвской метрикой // УМН. 2020. Т. 75. № 5 (455). С. 191–192.

  12. Сагдеев А.А. Об одной теореме Франкла–Уилсона // Пробл. передачи информ. 2019. Т. 55. № 4. С. 86–106.

  13. Sagdeev A. A. On the Chromatic Numbers Corresponding to Exponentially Ramsey Sets // J. Math. Sciences. 2020. V. 247. № 3. P. 488–497.

  14. Шабанов Д.А., Шайхеева Т.М. О предписанном хроматическом числе полных многодольных гиперграфов и кратных покрытиях независимыми множествами // Матем. заметки. 2020. Т. 107. № 3. С. 454–465.

  15. Semenov A., Shabanov D. On the weak chromatic number of random hypergraphs // Discrete Applied Mathematics. 2020. V. 276. P. 134–154.

  16. Akhmejanova M.B., Shabanov D.A. Equitable colorings of hypergraphs with few edges // Discrete Applied Mathematics. 2020. V. 276. P. 2–12.

  17. Пушняков Ф.А., Райгородский А.М. Оценка числа ребер в особых подграфах некоторого дистанционного графа // Матем. заметки. 2020. Т. 107. № 2. С. 286–298.

  18. Пушняков Ф.А., Райгородский А.М. Оценка числа ребер в подграфах графов Джонсона // Доклады РАН. Математика, информатика, процессы управления. 2021. Т. 499. С. 40–43.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал