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

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

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

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

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

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

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

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

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

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

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

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

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

Ключевым результатом о псевдослучайности графов является теорема Чанга–Грэма–Уилсона, которая утверждает, что многие из вышеприведенных условий эквивалентны с точностью до полиномиальных изменений в ^[3] . Последовательность графов, которая удовлетворяет этим условиям, называется квазислучайной . Считается особенно удивительным ^{[2] :9} , что слабое условие наличия «правильной» 4-цикловой плотности подразумевает другие, казалось бы, гораздо более сильные условия псевдослучайности. Такие графы, как 4-цикл, плотность которых в последовательности графов достаточна для проверки квазислучайности последовательности, известны как вынуждающие графы . ${\displaystyle \varepsilon }$

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

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

${\displaystyle \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-циклов сумма квадратов кодовых степеней ограничена:

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

Поэтому неравенство Коши–Шварца дает

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

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

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

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

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

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

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

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

Аналоги теоремы Чанга–Грэма–Уилсона

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

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

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

Последствия ограничения собственных значений

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

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

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

Связь с теоремой Грина–Тао

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

Ссылки

1. Томасон, Эндрю (1987). «Псевдослучайные графы». Annals of Discrete Math . North-Holland Mathematics Studies. 33 : 307–331. doi :10.1016/S0304-0208(08)73063-9. ISBN 978-0-444-70265-4.
2. Кривелевич, Майкл; Судаков, Бенни (2006). "Псевдослучайные графы" (PDF) . Еще множества, графы и числа . Математические исследования общества Бойяи. Том 15. С. 199–262. doi :10.1007/978-3-540-32439-3_10. ISBN 978-3-540-32377-8. S2CID  1952661.
3. Chung, FRK; Graham, RL; Wilson, RM (1989). «Квазислучайные графы» (PDF) . Combinatorica . 9 (4): 345–362. doi :10.1007/BF02125347. S2CID  17166765.
4. Симоновиц, Миклош; Сос, Вера (1991). «Разделение Семереди и квазислучайность». Случайные структуры и алгоритмы . 2 : 1–10. дои : 10.1002/rsa.3240020102.
5. Конлон, Дэвид; Чжао, Юфэй (2017). «Квазислучайные графы Кэли». Дискретный анализ . 6. arXiv : 1603.03025 . doi : 10.19086 /da.1294. S2CID  56362932.
6. Фридман, Джоэл (2003). «Относительные экспандеры или слабо относительно графы Рамануджана». Duke Math. J . 118 (1): 19–35. doi :10.1215/S0012-7094-03-11812-8. MR  1978881.
7. Кривелевич, Майкл; Судаков, Бенни; Ву, Ван Х.; Вормальд, Николас К. (2001). «Случайные регулярные графы высокой степени». Случайные структуры и алгоритмы . 18 (4): 346–363. doi :10.1002/rsa.1013. S2CID  16641598.
8. Алон, Нога; Кривелевич, Михаил; Судаков, Бенни (1999). «Раскраска списком случайных и псевдослучайных графов». Combinatorica . 19 (4): 453–472. doi :10.1007/s004939970001. S2CID  5724231.
9. Конлон, Дэвид ; Фокс, Джейкоб ; Чжао, Юфэй (2014). «Теорема Грина–Тао: изложение». Обзоры EMS по математическим наукам . 1 (2): 249–282. arXiv : 1403.2957 . doi :10.4171/EMSS/6. MR  3285854. S2CID  119301206.