Зависимый случайный выбор

В математике зависимый случайный выбор — это вероятностный метод, который показывает, как найти большой набор вершин в плотном графе так, чтобы каждое небольшое подмножество вершин имело много общих соседей. Это полезный инструмент для встраивания одного графа в другой граф с множеством ребер. Таким образом, она находит применение в экстремальной теории графов , аддитивной комбинаторике и теории Рамсея .

Формулировка теоремы

Позволять $u,n,r,m,t\in \mathbb {N}$ , $\alpha >0$ и предположим: ^[1]^[2]^[3]^[4]^[5] $n\alpha ^{t}-{n \choose r}\left({\frac {m}{n}}\right)^{t}\geq u.$ Каждый график на $n$ вершины с по крайней мере ${\frac {\alpha n^{2}}{2}}$ ребра содержат подмножество $U$ вершин с $|U|\geq u$ такой, что для всех $S\subset U$ с $|S|=r$ , $S$ имеет по крайней мере $m$ общие соседи.

Доказательство

Основная идея состоит в том, чтобы выбрать набор вершин случайным образом. Однако вместо равномерного случайного выбора каждой вершины процедура случайным образом выбирает список вершин. $t$ сначала вершины, а затем выбирает общих соседей в качестве набора вершин. Есть надежда, что таким образом выбранный набор с большей вероятностью будет иметь больше общих соседей.

Формально пусть $T$ быть списком $t$ вершины, выбранные равномерно случайным образом из $V(G)$ с заменой (допуская повторение). Позволять $A$ быть общим соседом $T$ . Ожидаемая стоимость $|A|$ является ${\begin{aligned}\mathbb {E} |A|&=\sum _{v\in V}\mathbb {P} (v\in A)=\sum _{v\in V}\mathbb {P} (T\subseteq N(v))=\sum _{v\in V}\left({\frac {d(v)}{n}}\right)^{t}\\&\geq n\left({\frac {1}{n}}\sum _{v\in V}{\frac {d(v)}{n}}\right)^{t}\quad {\text{(convexity)}}\\&\geq n\alpha ^{t}.\end{aligned}}$ Для каждого $r$ -подмножество элементов $S$ из $V$ , $A$ содержит $S$ тогда и только тогда, когда $T$ содержится в общей окрестности $S$ , что происходит с вероятностью ${\textstyle \left({\frac {\#{\text{common neighbors of }}S}{n}}\right)^{t}.}$ Ан $S$ плохо , если его меньше $m$ общие соседи. Тогда для каждого фиксированного $r$ -подмножество элементов $S$ из $V$ , он содержится в $A$ с вероятностью меньше $(m/n)^{t}$ . Следовательно, в силу линейности ожидания $\mathbb {E} [\#{\text{bad }}r{\text{-element subset of }}A]<{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}.$ Чтобы исключить плохие подмножества, мы исключаем один элемент в каждом плохом подмножестве. Число оставшихся элементов не менее $|A|-(\#{\text{bad }}r{\text{-element subset of }}A)$ , чье математическое ожидание не менее ${\textstyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq u.}$ Следовательно, существует $T$ такие, что есть хотя бы $u$ элементы в $A$ оставшееся после избавления от всего плохого $r$ -подмножества элементов. Набор $U$ из оставшихся $u$ элементы выражают желаемые свойства.

Приложения

Числа Турана двудольного графа

Зависимый случайный выбор может помочь найти число Турана . Используя соответствующие параметры, если $H=A\cup B$ — двудольный граф , в котором все вершины $B$ иметь высшее образование максимум $r$ , то экстремальное число ${\text{ex}}(n,H)\leq cn^{2-1/r}$ где $c=c(H)$ зависит только от $H$ . ^[1]^[5]

Формально с $a=|A|,b=|B|$ , позволять $c$ — достаточно большая константа такая, что $(2c)^{r}-(a+b)^{r}\geq a.$ Если $\alpha =2cn^{-1/r},m=a+b,t=r,u=a$ затем

$n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}=(2c)^{r}-{\binom {n}{r}}\left({\frac {a+b}{n}}\right)^{r}\geq (2c)^{r}-(a+b)^{r}\geq a=u,$ и поэтому предположение о зависимом случайном выборе справедливо. Следовательно, для каждого графа $G$ по крайней мере $cn^{2-1/r}$ ребра, существует подмножество вершин $U$ размера $a$ удовлетворение, что каждый $r$ -подмножество $U$ имеет по крайней мере $a+b$ общие соседи. Путем внедрения $H$ в $G$ путем внедрения $A$ в $U$ произвольно, а затем встраивая вершины в $B$ по одному, затем для каждой вершины $v$ в $B$ , оно имеет не более $r$ соседи по $A$ , что показывает, что их изображения в $U$ иметь по крайней мере $a+b$ общие соседи. Таким образом $v$ может быть встроен в одного из общих соседей, избегая при этом коллизий.

Это можно обобщить на вырожденные графы, используя вариант зависимого случайного выбора.

Встраивание 1-подразделения полного графа

DRC можно применить непосредственно, чтобы показать, что если $G$ это график на $n$ вершины и $\epsilon n^{2}$ края, затем $G$ содержит 1-подразделение полного графа с $\epsilon ^{3/2}n^{1/2}$ вершины. Это можно показать аналогично приведенному выше доказательству оценки числа Турана двудольного графа. ^[1]

Действительно, если мы положим $\alpha =2\epsilon ,m=a^{2},t={\frac {\log n}{2\log 1/\epsilon }},u=a$ , мы имеем (поскольку $2\epsilon =\alpha \leq 1$ ) $n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq (2\epsilon )^{t}n-{\binom {n}{2}}\epsilon ^{3t}\geq n^{1/2}\geq a=u,$ и поэтому предположение о ДРК справедливо. Поскольку 1-разбиение полного графа на $a$ вершин — двудольный граф с частями размера $a$ и $b={\binom {a}{2}}$ где каждая вершина во второй части имеет степень два, аргумент встраивания в доказательстве оценки числа Турана двудольного графа дает желаемый результат.

Вариация

Более сильная версия находит два подмножества вершин. $U_{1},U_{2}$ в плотном графе $G$ так что каждое небольшое подмножество вершин в $U_{i}$ имеет много общих соседей $U_{3-i}$ .

Формально пусть $u,n,r,m,t,q$ — некоторые положительные целые числа с $q>r$ , и пусть $\alpha >0$ быть некоторым действительным числом. Предположим, что выполнены следующие ограничения: ${\begin{aligned}n\alpha ^{t}-{\binom {n}{q}}\left({\frac {m}{n}}\right)^{t}&\geq u\\{\binom {n}{r}}\left({\frac {m}{u}}\right)^{q-r}&<1.\end{aligned}}$ Тогда каждый график $G$ на $n$ вершины с по крайней мере $\alpha n^{2}/2$ ребра содержат два подмножества $U_{1},U_{2}$ вершин так, что любой $r$ вершины в $U_{i}$ иметь по крайней мере $m$ общие соседи по $U_{3-i}$ . ^[1]

Экстремальное число вырожденного двудольного графа

Используя это более сильное утверждение, можно оценить сверху экстремальное число $r$ -вырожденные двудольные графы: для каждого $r$ -вырожденный двудольный граф $H$ с максимум $N^{1-1.8/s}$ вершин, экстремальное число ${\text{ex}}(N,H)$ самое большее $N^{2-1/(s^{3}r)}.$ ^[1]

Число Рамсея вырожденного двудольного графа

Это утверждение можно также применить для получения верхней оценки числа Рамсея вырожденных двудольных графов. Если $r$ — фиксированное целое число, то для любого двудольного $r$ -вырожденный двудольный граф $G$ на $n$ вершины, число Рамсея $r(G)$ имеет порядок $n^{1+o(1)}.$ ^[1]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Фокс, Джейкоб; Судаков, Бенни (2011). «Зависимый случайный выбор». Случайные структуры и алгоритмы . 38 (1–2): 68–99. дои : 10.1002/rsa.20344 . hdl : 1721.1/70097 . ISSN 1098-2418 . S2CID 2321395 .
^ Верстраэте, Жак (2015). «6 — Зависимый случайный выбор» (PDF) . Калифорнийский университет в Сан-Диего . S2CID 47638896 . Архивировано из оригинала (PDF) 19 мая 2017 г.
^ Косточка, А.В.; Рёдль, В. (2001). «О графах с малыми числами Рамсея*». Журнал теории графов . 37 (4): 198–204. CiteSeerX 10.1.1.225.1347 . дои : 10.1002/jgt.1014 . ISSN 1097-0118 . S2CID 12292577 .
^ Судаков, Бенни (1 мая 2003 г.). «Несколько замечаний о задачах типа Рэмси – Турана» . Журнал комбинаторной теории . Серия Б. 88 (1): 99–106. дои : 10.1016/S0095-8956(02)00038-2 . ISSN 0095-8956 .
^ Jump up to: ^а ^б Алон, Нога; Кривелевич, Михаил; Судаков, Бенни (ноябрь 2003 г.). «Числа Турана для двудольных графов и связанные с ними вопросы типа Рамсея». Комбинаторика, теория вероятностей и вычисления . 12 (5+6): 477–494. дои : 10.1017/S0963548303005741 . ISSN 1469-2163 .

Дальнейшее чтение