Зависимый случайный выбор - Dependent random choice

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

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

^{[1][2][3][4][5]}Позволять ${\displaystyle u,n,r,m,t\in \mathbb {N} }$, ${\displaystyle \alpha >0}$ и предположим

$${\displaystyle n\alpha ^{t}-{n \choose r}\left({\frac {m}{n}}\right)^{t}\geq u.}$$

Тогда каждый граф на ${\displaystyle n}$ вершины не менее ${\displaystyle {\frac {\alpha n^{2}}{2}}}$ ребра содержат подмножество ${\displaystyle U}$ вершин с ${\displaystyle |U|\geq u}$ такой, что для всех ${\displaystyle S\subset U}$ с участием ${\displaystyle |S|=r}$, ${\displaystyle S}$ имеет по крайней мере ${\displaystyle m}$ общие соседи.

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

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

Формально пусть ${\displaystyle T}$ быть списком ${\displaystyle t}$ вершины выбираются равномерно случайным образом из ${\displaystyle V(G)}$ с заменой (с возможностью повторения). Позволять ${\displaystyle A}$ быть обычным соседством ${\displaystyle T}$. Ожидаемая стоимость ${\displaystyle |A|}$ является

$${\displaystyle {\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}}}$$

Для каждого ${\displaystyle r}$-элементное подмножество ${\displaystyle S}$ из ${\displaystyle V}$, событие ${\displaystyle A}$ содержащий ${\displaystyle S}$ происходит тогда и только тогда, когда ${\displaystyle T}$ содержится в общей окрестности ${\displaystyle S}$, что происходит с вероятностью ${\textstyle \left({\frac {\#{\text{common neighbors of }}S}{n}}\right)^{t}.}$ Позвоните в ${\displaystyle S}$ плохой если у него меньше чем ${\displaystyle m}$ общие соседи. Тогда для каждого фиксированного ${\displaystyle r}$-элементное подмножество ${\displaystyle S}$ из ${\displaystyle V}$, он содержится в ${\displaystyle A}$ с вероятностью меньше чем ${\displaystyle (m/n)^{t}}$. Следовательно, по линейности ожидания

$${\displaystyle \mathbb {E} [\#{\text{bad }}r{\text{-element subset of }}A]<{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}.}$$

Чтобы убедиться, что нет плохих подмножеств, мы можем избавиться от одного элемента в каждом плохом подмножестве. Количество оставшихся элементов не менее ${\displaystyle |A|-(\#{\text{bad }}r{\text{-element subset of }}A)}$, ожидаемое значение которого не менее ${\textstyle n\alpha ^{t}-{\binom {n}{r}}\left({\frac {m}{n}}\right)^{t}\geq u.}$ Следовательно, существует ${\displaystyle T}$ так что есть по крайней мере ${\displaystyle u}$ элементы в ${\displaystyle A}$ остающийся после избавления от всего плохого ${\displaystyle r}$-элементные подмножества. Набор ${\displaystyle U}$ из оставшихся ${\displaystyle u}$ elements удовлетворяет желаемым свойствам.

Приложения

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

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

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

$${\displaystyle 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,}$$

Таким образом, выполняется предположение о зависимом случайном выборе. Следовательно, для каждого графа ${\displaystyle G}$ по крайней мере с ${\displaystyle cn^{2-1/r}}$ ребер существует подмножество вершин ${\displaystyle U}$ размера ${\displaystyle a}$ удовлетворение того, что каждый ${\displaystyle r}$-подмножество ${\displaystyle U}$ имеет по крайней мере ${\displaystyle a+b}$ общие соседи. Это позволяет нам встроить ${\displaystyle H}$ в ${\displaystyle G}$ следующим образом. Встроить ${\displaystyle A}$ в ${\displaystyle U}$ произвольно, а затем вложим вершины в ${\displaystyle B}$ по одному. Для каждой вершины ${\displaystyle v}$ в ${\displaystyle B}$, у него не больше ${\displaystyle r}$ соседи в ${\displaystyle A}$, что показывает, что их изображения в ${\displaystyle U}$ иметь по крайней мере ${\displaystyle a+b}$ общие соседи. Это позволяет нам встроить ${\displaystyle v}$ одному из общих соседей, избегая столкновений.

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

Встраивание 1-секционный полного графа

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

Действительно, если положить ${\displaystyle \alpha =2\epsilon ,m=a^{2},t={\frac {\log n}{2\log 1/\epsilon }},u=a}$, имеем (так как ${\displaystyle 2\epsilon =\alpha \leq 1}$)

$${\displaystyle 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-разбиение полного графа на ${\displaystyle a}$ вершины - двудольный граф с частями размера ${\displaystyle a}$ и ${\displaystyle b={\binom {a}{2}}}$ где каждая вершина во второй части имеет степень два, мы можем использовать аргумент вложения в приведенном выше доказательстве оценки Число Турана двудольного графа, чтобы получить желаемый результат.

Вариация

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

Формально пусть ${\displaystyle u,n,r,m,t,q}$ быть некоторыми положительными целыми числами с ${\displaystyle q>r}$, и разреши ${\displaystyle \alpha >0}$ быть реальным числом. Предположим, что выполняются следующие ограничения:

$${\displaystyle {\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}}}$$

Тогда каждый граф ${\displaystyle G}$ на ${\displaystyle n}$ вершины не менее ${\displaystyle \alpha n^{2}/2}$ ребра содержит два подмножества ${\displaystyle U_{1},U_{2}}$ вершин так, чтобы любая ${\displaystyle r}$ вершины в ${\displaystyle U_{i}}$ иметь по крайней мере ${\displaystyle m}$ общие соседи в ${\displaystyle U_{3-i}}$.^[1]

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

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

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

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

использованная литература

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

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

• Зависимый случайный выбор - MIT Math