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

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

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

| е ( У ) − п ( | У | 2 ) | ≤ α | У | {\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}}))} 2 н {\displaystyle 2n} н {\displaystyle n} н {\displaystyle n} ( п , α ) {\displaystyle (p,\альфа)} α {\displaystyle \альфа}

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

Thomason показал, что условие "перемешанности" подразумевается более простым для проверки условием, зависящим только от кодовой степени двух вершин, а не каждого подмножества множества вершин графа. Положим, что будет числом общих соседей двух вершин и , Thomason показал, что, если задан граф на вершинах с минимальной степенью , если для каждого и , то является -перемешанным. [2] : 7  Этот результат показывает, как проверить условие перемешанности алгоритмически за полиномиальное время от числа вершин, и может быть использован для демонстрации псевдослучайности конкретных графов. [2] : 7  кодег ⁡ ( ты , в ) {\displaystyle \operatorname {codeg} (u,v)} ты {\displaystyle u} в {\displaystyle v} Г {\displaystyle G} н {\displaystyle n} н п {\displaystyle np} кодег ⁡ ( ты , в ) ≤ н п 2 + ℓ {\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} ε > 0 {\displaystyle \varepsilon >0}

  • Несоответствие : для любого подмножества множества вершин число ребер между и находится в пределах . Х , И {\displaystyle X,Y} В = В ( Г ) {\displaystyle V=V(G)} Х {\displaystyle X} И {\displaystyle Y} ε н 2 {\displaystyle \varepsilon n^{2}} п | Х | | И | {\displaystyle p|X||Y|}
  • Расхождение по отдельным наборам : для любого подмножества число ребер среди находится в пределах . Х {\displaystyle X} В {\displaystyle V} Х {\displaystyle X} ε н 2 {\displaystyle \varepsilon n^{2}} п ( | Х | 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-циклов : число помеченных -циклов среди подграфов находится в пределах . 4 {\displaystyle 4} Г {\displaystyle G} ε н 4 {\displaystyle \varepsilon n^{4}} п 4 н 4 {\displaystyle p^{4}n^{4}}
  • Кодовая степень : пусть будет числом общих соседей двух вершин и , кодег ⁡ ( ты , в ) {\displaystyle \operatorname {codeg} (u,v)} ты {\displaystyle u} в {\displaystyle v}
∑ ты , в ∈ В | кодег ⁡ ( ты , в ) − п 2 н | ≤ ε н 3 . {\displaystyle \sum _{u,v\in V}{\big |}\operatorname {codeg} (u,v)-p^{2}n{\big |}\leq \varepsilon n^{3} .}
  • Ограничение собственных значений : если — собственные значения матрицы смежности , то находится в пределах и . λ 1 ≥ λ 2 ≥ ⋯ ≥ λ н {\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}} Г {\displaystyle G} λ 1 {\displaystyle \лямбда _{1}} ε н {\displaystyle \varepsilon n} п н {\displaystyle pn} макс ( | λ 2 | , | λ н | ) ≤ ε н {\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} ( п + о ( 1 ) ) ( н 2 ) {\displaystyle (p+o(1)){\binom {n}{2}}} ЧАС {\displaystyle H} Г н {\displaystyle G_{n}} ( п е ( ЧАС ) + о ( 1 ) ) е в ( ЧАС ) {\displaystyle \left(p^{e(H)}+o(1)\right)e^{v(H)}} н → ∞ {\displaystyle n\to \infty } | е ( Х , И ) − п | Х | | И | | = о ( н 2 ) {\displaystyle \left|e(X,Y)-p|X||Y|\right|=o(n^{2})}

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

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

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

∑ ты , в ∈ Г кодег ⁡ ( ты , в ) = ∑ х ∈ Г градус ⁡ ( х ) 2 ≥ н ( 2 е ( Г ) н ) 2 = ( п 2 + о ( 1 ) ) н 3 . {\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-циклов сумма квадратов кодовых степеней ограничена:

∑ ты , в кодег ⁡ ( ты , в ) 2 = Количество маркированных копий  С 4 + о ( н 4 ) ≤ ( п 4 + о ( 1 ) ) н 4 . {\displaystyle \sum _{u,v}\operatorname {codeg} (u,v)^{2}={\text{Количество помеченных копий }}C_{4}+o(n^{4})\leq \left(p^{4}+o(1)\right)n^{4}.}

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

∑ ты , в ∈ Г | кодег ⁡ ( ты , в ) − п 2 н | ≤ н ( ∑ ты , в ∈ Г ( кодег ⁡ ( ты , в ) − п 2 н ) 2 ) 1 / 2 , {\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} о ( 1 ) {\displaystyle o(1)} тр ⁡ ( А Г 4 ) {\displaystyle \operatorname {tr} \left(A_{G}^{4}\right)} А Г {\displaystyle A_{G}} Г {\displaystyle G}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдослучайные графы играют важную роль в доказательстве теоремы Грина–Тао . Теорема доказывается путем переноса теоремы Семереди , утверждения о том, что множество положительных целых чисел с положительной натуральной плотностью содержит произвольно длинные арифметические прогрессии, на разреженную установку (поскольку простые числа имеют естественную плотность в целых числах). Перенос на разреженные множества требует, чтобы множества вели себя псевдослучайно, в том смысле, что соответствующие графы и гиперграфы имеют правильные плотности подграфов для некоторого фиксированного множества небольших (гипер)подграфов. [9] Затем показано, что подходящее надмножество простых чисел, называемое псевдопростыми числами, в котором простые числа плотны, подчиняется этим условиям псевдослучайности, завершая доказательство. 0 {\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. ^ abcdefg Кривелевич, Майкл; Судаков, Бенни (2006). "Псевдослучайные графы" (PDF) . Еще множества, графы и числа . Математические исследования общества Бойяи. Том 15. С.  199– 262. doi :10.1007/978-3-540-32439-3_10. ISBN 978-3-540-32377-8. S2CID  1952661.
  3. ^ abc Chung, FRK; Graham, RL; Wilson, RM (1989). «Квазислучайные графы» (PDF) . Combinatorica . 9 (4): 345– 362. doi :10.1007/BF02125347. S2CID  17166765.
  4. ^ Симоновиц, Миклош; Сос, Вера (1991). «Разделение Семереди и квазислучайность». Случайные структуры и алгоритмы . 2 : 1–10 . doi :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. ^ ab Алон, Нога; Кривелевич, Михаил; Судаков, Бенни (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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pseudorandom_graph&oldid=1253319143"