Псевдослучайный граф

В теории графов граф называется псевдослучайным, если он подчиняется определенным свойствам, которым случайные графы подчиняются с высокой вероятностью . Не существует конкретного определения псевдослучайности графа , но существует множество разумных характеристик псевдослучайности, которые можно рассмотреть.

Псевдослучайные свойства впервые были официально рассмотрены Эндрю Томасоном в 1987 году. Он определил состояние, называемое «перемешанностью»: граф $G=(V,E)$ Говорят, что это $(p,\alpha )$- перепутал по-настоящему $p$ и $\alpha$ с $0<p<1\leq \alpha$ если

$\left|e(U)-p{\binom {|U|}{2}}\right|\leq \alpha |U|$

для каждого подмножества $U$ множества вершин $V$, где $e(U)$ количество ребер среди $U$ (эквивалентно количеству ребер в подграфе, индуцированном множеством вершин $U$). Можно показать, что Эрдеша – Реньи случайный граф $G(n,p)$ почти наверняка $(p,O({\sqrt {np}}))$- перепутал. Однако графы с менее равномерно распределенными ребрами, например граф на $2n$ вершины, состоящие из $n$-вершинный полный граф и $n$ полностью независимые вершины, не являются $(p,\alpha )$-перемешано для любого маленького $\alpha$, что делает беспорядочность разумным показателем «случайных» свойств распределения ребер графа.

Связь с местными условиями

Томасон показал, что условие «перемешательства» подразумевается более простым для проверки условием, зависящим только от костепени двух вершин, а не от каждого подмножества множества вершин графа. Сдача в аренду $\operatorname {codeg} (u,v)$ - количество общих соседей двух вершин $u$ и $v$, Томасон показал, что для данного графа $G$ на $n$ вершины минимальной степени $np$, если $\operatorname {codeg} (u,v)\leq np^{2}+\ell$ для каждого $u$ и $v$, затем $G$ является $\left(p,{\sqrt {(p+\ell )n}}\,\right)$- перепутал. Этот результат показывает, как алгоритмически проверить условие перемешанности за полиномиальное время по числу вершин, и может использоваться для демонстрации псевдослучайности конкретных графов.

Теорема Чанга–Грэма–Уилсона

В духе условий, рассмотренных Томасоном, и их поочередного глобального и локального характера, Чанг, Грэм и Уилсон в 1989 году рассмотрели несколько более слабых условий: график $G$ на $n$ вершины с плотностью ребер $p$ и некоторые $\varepsilon >0$ может удовлетворить каждому из этих условий, если

• Несоответствие : для любых подмножеств $X,Y$ множества вершин $V=V(G)$, количество ребер между $X$ и $Y$ находится внутри $\varepsilon n^{2}$ из $p|X||Y|$.
• Расхождение по отдельным наборам : для любого подмножества $X$ из $V$, количество ребер среди $X$ находится внутри $\varepsilon n^{2}$ из $p{\binom {|X|}{2}}$.
• Подсчет подграфов : для каждого графа $H$, количество помеченных копий $H$ среди подграфов $G$ находится внутри $\varepsilon n^{v(H)}$ из $p^{e(H)}n^{v(H)}$.
• 4-цикловый подсчет : количество меченых $4$-циклы среди подграфов $G$ находится внутри $\varepsilon n^{4}$ из $p^{4}n^{4}$.
• Костепень : сдача в аренду $\operatorname {codeg} (u,v)$ - количество общих соседей двух вершин $u$ и $v$,

$\sum _{u,v\in V}{\big |}\operatorname {codeg} (u,v)-p^{2}n{\big |}\leq \varepsilon n^{3}.$

• Ограничение собственных значений : если $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ являются собственными значениями смежности матрицы $G$, затем $\lambda _{1}$ находится внутри $\varepsilon n$ из $pn$ и $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon n$.

Все эти условия могут быть сформулированы в терминах последовательности графов $\{G_{n}\}$ где $G_{n}$ включен $n$ вершины с $(p+o(1)){\binom {n}{2}}$ края. Например, условием 4-циклового счета становится то, что количество копий любого графа $H$ в $G_{n}$ является $\left(p^{e(H)}+o(1)\right)e^{v(H)}$ как $n\to \infty$, и условие невязки принимает вид $\left|e(X,Y)-p|X||Y|\right|=o(n^{2})$, используя обозначение Little-o .

Ключевым результатом о псевдослучайности графов является теорема Чанга-Грэма-Уилсона, которая утверждает, что многие из вышеперечисленных условий эквивалентны, с точностью до полиномиальных изменений в $\varepsilon$. Последовательность графов, удовлетворяющая этим условиям, называется квазислучайной . Это считается особенно удивительным что слабое условие наличия «правильной» плотности 4-циклов подразумевает другие, казалось бы, гораздо более сильные условия псевдослучайности. Графы типа 4-цикла, плотность которых в последовательности графов достаточна для проверки квазислучайности последовательности, известны как форсирующие графы .

Некоторые следствия из теоремы Чанга-Грэма-Уилсона ясны из определений условий: условие несоответствия отдельных множеств - это просто частный случай условия несоответствия для $Y=X$, а 4-цикловый подсчет является частным случаем подсчета подграфов. Кроме того, лемма о подсчете графов, прямое обобщение леммы о подсчете треугольников , подразумевает, что условие несоответствия подразумевает подсчет подграфов.

Тот факт, что 4-цикловый счет подразумевает условие костепени, можно доказать с помощью метода, аналогичного методу второго момента. Во-первых, сумма костепеней может быть ограничена сверху:

$\sum _{u,v\in G}\operatorname {codeg} (u,v)=\sum _{x\in G}\deg(x)^{2}\geq n\left({\frac {2e(G)}{n}}\right)^{2}=\left(p^{2}+o(1)\right)n^{3}.$

Для 4-циклов сумма квадратов костепеней ограничена:

$\sum _{u,v}\operatorname {codeg} (u,v)^{2}={\text{Number of labeled copies of }}C_{4}+o(n^{4})\leq \left(p^{4}+o(1)\right)n^{4}.$

Следовательно, неравенство Коши – Шварца дает

$\sum _{u,v\in G}|\operatorname {codeg} (u,v)-p^{2}n|\leq n\left(\sum _{u,v\in G}\left(\operatorname {codeg} (u,v)-p^{2}n\right)^{2}\right)^{1/2},$

которое можно расширить, используя наши границы на первый и второй моменты $\operatorname {codeg}$ чтобы дать желаемую границу. Доказательство того, что из условия костепени следует условие невязки, можно провести с помощью аналогичного, хотя и более сложного, вычисления с использованием неравенства Коши – Шварца.

Условие собственных значений и условие 4-циклов можно связать, заметив, что количество помеченных 4-циклов в $G$ есть, до $o(1)$ вытекающие из вырожденных 4-циклов, $\operatorname {tr} \left(A_{G}^{4}\right)$, где $A_{G}$ является матрицей смежности $G$. Затем можно показать, что эти два условия эквивалентны, применив теорему Куранта – Фишера .

Связь с регулярностью графика

Концепция графов, которые действуют как случайные графы, тесно связана с концепцией регулярности графа, используемой в лемме о регулярности Семереди . Для $\varepsilon >0$, пара наборов вершин $X,Y$ называется $\varepsilon$-регулярный , если для всех подмножеств $A\subset X,B\subset Y$ удовлетворяющий $|A|\geq \varepsilon |X|,|B|\geq \varepsilon |Y|$, он утверждает, что

$\left|d(X,Y)-d(A,B)\right|\leq \varepsilon ,$

где $d(X,Y)$ обозначает плотность краев между $X$ и $Y$: количество ребер между $X$ и $Y$ разделенный на $|X||Y|$. Это условие подразумевает двудольный аналог условия несоответствия и, по сути, утверждает, что края между $A$ и $B$ вести себя «случайным» образом. в 1991 году показали Кроме того, Миклош Симоновиц и Вера Т. Сос , что граф удовлетворяет указанным выше слабым условиям псевдослучайности, используемым в теореме Чунга – Грэма – Вильсона, тогда и только тогда, когда он обладает разбиением Семереди, где почти все плотности близки к плотность ребер всего графа.

Разреженная псевдослучайность

Чанга–Грэма–

Теорема Чанга-Грэма-Уилсона, в частности, следствие подсчета подграфов по несоответствию, не следует для последовательностей графов с плотностью ребер, приближающейся к $0$или, например, общий случай $d$- регулярные графики на $n$ вершины как $n\to \infty$. Обычно рассматриваются следующие разреженные аналоги условий невязки и ограничений на собственные значения:

• Редкое несоответствие : для любых подмножеств $X,Y$ множества вершин $V=V(G)$, количество ребер между $X$ и $Y$ находится внутри $\varepsilon dn$ из ${\frac {d}{n}}|X||Y|$.
• Разреженное ограничение собственных значений : если $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ являются собственными значениями смежности матрицы $G$, затем $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon d$.

Обычно верно, что это условие собственных значений влечет за собой соответствующее условие невязки, но обратное неверно: непересекающееся объединение случайных больших чисел $d$-регулярный граф и $d+1$-вершинный полный граф имеет два собственных значения ровно $d$ но, вероятно, удовлетворяет свойству несоответствия. Однако, как доказали Дэвид Конлон и Юфэй Чжао в 2017 году, небольшие варианты условий несоответствия и собственных значений для $d$-регулярные графы Кэли эквивалентны с точностью до линейного масштабирования в $\varepsilon$. Одно направление этого следует из леммы о смешивании расширителей , тогда как другое требует предположения, что граф является графом Кэли и использует неравенство Гротендика .

ограничения

А $d$-регулярный график $G$ на $n$ вершин называется $(n,d,\lambda )$-график, если, допуская собственные значения матрицы смежности $G$ быть $d=\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$, $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \lambda$. Граница Алона -Боппаны дает это $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\geq 2{\sqrt {d-1}}-o(1)$ (где $o(1)$ срок такой $n\to \infty$), а Джоэл Фридман доказал, что случайное $d$-регулярный график на $n$ вершины $(n,d,\lambda )$ для $\lambda =2{\sqrt {d-1}}+o(1)$. В этом смысле насколько $\lambda$ превышает $2{\sqrt {d-1}}$ является общей мерой неслучайности графа. Есть графики с $\lambda \leq 2{\sqrt {d-1}}$, которые называются графами Рамануджана . Они широко изучены, и существует ряд открытых проблем, связанных с их существованием и распространенностью.

Учитывая $(n,d,\lambda )$ график для маленьких $\lambda$, многие стандартные величины теории графов могут быть ограничены примерно так, как можно было бы ожидать от случайного графа. В частности, размер $\lambda$ оказывает прямое влияние на несоответствия плотности ребер подмножества через лемму о смешивании расширителей. Другие примеры таковы, позволяя $G$ быть $(n,d,\lambda )$ график:

• Если $d\leq {\frac {n}{2}}$, вершинная связность $\kappa (G)$ из $G$ удовлетворяет $\kappa (G)\geq d-{\frac {36\lambda ^{2}}{d}}.$
• Если $\lambda \leq d-2$, $G$ является $d$ с краевым соединением . Если $n$ даже, $G$ содержит идеальное совпадение.
• Максимальный разрез ​ $G$ самое большее ${\frac {n(d+\lambda )}{4}}$.
• Самое большое независимое подмножество подмножества $U\subset V(G)$ в $G$ имеет размер как минимум ${\frac {n}{2(d-\lambda )}}\ln \left({\frac {|U|(d-\lambda )}{n(\lambda +1)}}+1\right).$
• Хроматическое число ​ $G$ самое большее ${\frac {6(d-\lambda )}{\ln \left({\frac {d+1}{\lambda +1}}\right)}}.$

Грина-

Псевдослучайные графы играют важную роль в доказательстве теоремы Грина–Тао . Теорема доказывается путем переноса теоремы Семереди , утверждения о том, что набор положительных целых чисел с положительной натуральной плотностью содержит сколь угодно длинные арифметические прогрессии, в разреженную среду (поскольку простые числа имеют естественную плотность $0$ в целых числах). Переход к разреженным множествам требует, чтобы множества вели себя псевдослучайно в том смысле, что соответствующие графы и гиперграфы имели правильную плотность подграфов для некоторого фиксированного набора маленьких (гипер)подграфов. Затем показано, что подходящее надмножество простых чисел, называемое псевдопростыми числами, в котором простые числа плотны, подчиняется этим условиям псевдослучайности, что завершает доказательство.