Псевдослучайный граф
В теории графов граф называется псевдослучайным, если он подчиняется определенным свойствам, которым случайные графы подчиняются с высокой вероятностью . Не существует конкретного определения псевдослучайности графа , но существует множество разумных характеристик псевдослучайности, которые можно рассмотреть.
Псевдослучайные свойства впервые были официально рассмотрены Эндрю Томасоном в 1987 году. [1] [2] Он определил состояние, называемое «перемешанностью»: граф Говорят, что это - перепутал по-настоящему и с если
для каждого подмножества множества вершин , где количество ребер среди (эквивалентно количеству ребер в подграфе, индуцированном множеством вершин ). Можно показать, что Эрдеша – Реньи случайный граф почти наверняка - перепутал. [2] : 6 Однако графы с менее равномерно распределенными ребрами, например граф на вершины, состоящие из -вершинный полный граф и полностью независимые вершины, не являются -перемешано для любого маленького , что делает беспорядочность разумным показателем «случайных» свойств распределения ребер графа.
Связь с местными условиями
[ редактировать ]Томасон показал, что условие «перемешательства» подразумевается более простым для проверки условием, зависящим только от костепени двух вершин, а не от каждого подмножества множества вершин графа. Сдача в аренду - количество общих соседей двух вершин и , Томасон показал, что для данного графа на вершины минимальной степени , если для каждого и , затем является - перепутал. [2] : 7 Этот результат показывает, как алгоритмически проверить условие перемешанности за полиномиальное время по числу вершин, и может использоваться для демонстрации псевдослучайности конкретных графов. [2] : 7
Теорема Чанга – Грэма – Вильсона
[ редактировать ]В духе условий, рассмотренных Томасоном, и их поочередного глобального и локального характера, Чанг, Грэм и Уилсон в 1989 году рассмотрели несколько более слабых условий: [3] график на вершины с плотностью ребер и некоторые может удовлетворить каждому из этих условий, если
- Несоответствие : для любых подмножеств множества вершин , количество ребер между и находится внутри из .
- Расхождение по отдельным наборам : для любого подмножества из , количество ребер среди находится внутри из .
- Подсчет подграфов : для каждого графа , количество помеченных копий среди подграфов находится внутри из .
- 4-цикловый подсчет : количество меченых -циклы среди подграфов находится внутри из .
- Костепень : сдача в аренду - количество общих соседей двух вершин и ,
- Ограничение собственных значений : если являются собственными значениями смежности матрицы , затем находится внутри из и .
Все эти условия могут быть сформулированы в терминах последовательности графов где включен вершины с края. Например, условием 4-циклового счета становится то, что количество копий любого графа в является как , и условие невязки принимает вид , используя обозначение Little-o .
Ключевым результатом о псевдослучайности графов является теорема Чанга-Грэма-Уилсона, которая утверждает, что многие из вышеперечисленных условий эквивалентны, с точностью до полиномиальных изменений в [3] . Последовательность графов, удовлетворяющая этим условиям, называется квазислучайной . Это считается особенно удивительным [2] : 9 что слабое условие наличия «правильной» плотности 4-циклов подразумевает другие, казалось бы, гораздо более сильные условия псевдослучайности. Графы типа 4-цикла, плотность которых в последовательности графов достаточна для проверки квазислучайности последовательности, известны как форсирующие графы .
Некоторые следствия из теоремы Чанга-Грэма-Уилсона ясны из определений условий: условие несоответствия отдельных множеств - это просто частный случай условия несоответствия для , а 4-цикловый подсчет является частным случаем подсчета подграфов. Кроме того, лемма о подсчете графов, прямое обобщение леммы о подсчете треугольников , подразумевает, что условие несоответствия подразумевает подсчет подграфов.
Тот факт, что 4-цикловый счет подразумевает условие костепени, можно доказать с помощью метода, аналогичного методу второго момента. Во-первых, сумма костепеней может быть ограничена сверху:
Для 4-циклов сумма квадратов костепеней ограничена:
Следовательно, неравенство Коши – Шварца дает
которое можно расширить, используя наши границы на первый и второй моменты чтобы дать желаемую границу. Доказательство того, что из условия костепени следует условие невязки, можно провести с помощью аналогичного, хотя и более сложного, вычисления с использованием неравенства Коши – Шварца.
Условие собственных значений и условие 4-циклов можно связать, заметив, что количество помеченных 4-циклов в есть, до вытекающие из вырожденных 4-циклов, , где является матрицей смежности . Затем можно показать, что эти два условия эквивалентны, применив теорему Куранта – Фишера . [3]
Связь с регулярностью графика
[ редактировать ]Концепция графов, которые действуют как случайные графы, тесно связана с концепцией регулярности графа, используемой в лемме о регулярности Семереди . Для , пара наборов вершин называется -регулярный , если для всех подмножеств удовлетворяющий , он утверждает, что
где обозначает плотность краев между и : количество ребер между и разделенный на . Это условие подразумевает двудольный аналог условия несоответствия и, по сути, утверждает, что края между и вести себя «случайным» образом. в 1991 году показали Кроме того, Миклош Симоновиц и Вера Т. Сос , что граф удовлетворяет указанным выше слабым условиям псевдослучайности, используемым в теореме Чунга – Грэма – Вильсона, тогда и только тогда, когда он обладает разбиением Семереди, где почти все плотности близки к плотность ребер всего графа. [4]
Редкая псевдослучайность
[ редактировать ]Аналоги теоремы Чанга – Грэма – Вильсона
[ редактировать ]Теорема Чанга-Грэма-Уилсона, в частности, следствие подсчета подграфов по несоответствию, не следует для последовательностей графов с плотностью ребер, приближающейся к или, например, общий случай - регулярные графики на вершины как . Обычно рассматриваются следующие разреженные аналоги условий невязки и ограничений на собственные значения:
- Редкое несоответствие : для любых подмножеств множества вершин , количество ребер между и находится внутри из .
- Разреженное ограничение собственных значений : если являются собственными значениями смежности матрицы , затем .
Обычно верно, что это условие собственных значений влечет за собой соответствующее условие невязки, но обратное неверно: непересекающееся объединение случайных больших чисел -регулярный граф и -вершинный полный граф имеет два собственных значения ровно но, вероятно, удовлетворяет свойству несоответствия. Однако, как доказали Дэвид Конлон и Юфэй Чжао в 2017 году, небольшие варианты условий несоответствия и собственных значений для -регулярные графы Кэли эквивалентны с точностью до линейного масштабирования в . [5] Одно направление этого следует из леммы о смешивании расширителей , тогда как другое требует предположения, что граф является графом Кэли и использует неравенство Гротендика .
Последствия ограничения собственных значений
[ редактировать ]А -регулярный график на вершин называется -график, если, допуская собственные значения матрицы смежности быть , . Граница Алона -Боппаны дает это (где срок такой ), а Джоэл Фридман доказал, что случайное -регулярный график на вершины для . [6] В этом смысле насколько превышает является общей мерой неслучайности графа. Есть графики с , которые называются графами Рамануджана . Они широко изучены, и существует ряд открытых проблем, связанных с их существованием и распространенностью.
Учитывая график для маленьких , многие стандартные величины теории графов могут быть ограничены примерно так, как можно было бы ожидать от случайного графа. В частности, размер оказывает прямое влияние на несоответствия плотности ребер подмножества через лемму о смешивании расширителей. Другие примеры таковы, позволяя быть график:
- Если , вершинная связность из удовлетворяет [7]
- Если , является с краевым соединением . Если даже, содержит идеальное совпадение. [2] : 32
- Максимальный разрез самое большее . [2] : 33
- Самое большое независимое подмножество подмножества в имеет размер как минимум [8]
- Хроматическое число самое большее [8]
Связь с теоремой Грина – Тао
[ редактировать ]Псевдослучайные графы играют важную роль в доказательстве теоремы Грина–Тао . Теорема доказывается путем переноса теоремы Семереди , утверждения о том, что набор положительных целых чисел с положительной натуральной плотностью содержит сколь угодно длинные арифметические прогрессии, в разреженную среду (поскольку простые числа имеют естественную плотность в целых числах). Переход к разреженным множествам требует, чтобы множества вели себя псевдослучайно в том смысле, что соответствующие графы и гиперграфы имели правильную плотность подграфов для некоторого фиксированного набора маленьких (гипер)подграфов. [9] Затем показано, что подходящее надмножество простых чисел, называемое псевдопростыми числами, в котором простые числа плотны, подчиняется этим условиям псевдослучайности, что завершает доказательство.
Ссылки
[ редактировать ]- ^ Томасон, Эндрю (1987). «Псевдослучайные графы» . Анналы дискретной математики . 33 : 307–331.
- ^ Перейти обратно: а б с д и ж г Кривелевич, Михаил; Судаков, Бенни (2006). «Псевдослучайные графики» (PDF) . Больше наборов, графиков и чисел . Общество математических исследований Боляи. Том. 15. стр. 199–262. дои : 10.1007/978-3-540-32439-3_10 . ISBN 978-3-540-32377-8 . S2CID 1952661 .
- ^ Перейти обратно: а б с Чанг, Франция; Грэм, РЛ; Уилсон, Р.М. (1989). «Квазислучайные графики» (PDF) . Комбинаторика . 9 (4): 345–362. дои : 10.1007/BF02125347 . S2CID 17166765 .
- ^ Симоновиц, Миклош; Сос, Вера (1991). «Разделение Семереди и квазислучайность». Случайные структуры и алгоритмы . 2 : 1–10. дои : 10.1002/rsa.3240020102 .
- ^ Конлон, Дэвид; Чжао, Юфэй (2017). «Квазислучайные графы Кэли». Дискретный анализ . 6 . arXiv : 1603.03025 . дои : 10.19086/da.1294 . S2CID 56362932 .
- ^ Фридман, Джоэл (2003). «Относительные расширители или слабо относительно графы Рамануджана». Герцог Мат. Дж . 118 (1): 19–35. дои : 10.1215/S0012-7094-03-11812-8 . МР 1978881 .
- ^ Кривелевич, Михаил; Судаков, Бенни; Ву, Ван Х.; Вормальд, Николас К. (2001). «Случайные регулярные графы высокой степени». Случайные структуры и алгоритмы . 18 (4): 346–363. дои : 10.1002/rsa.1013 . S2CID 16641598 .
- ^ Перейти обратно: а б Алон, Нога; Кривелевич, Михаил; Судаков, Бенни (1999). «Списковая раскраска случайных и псевдослучайных графов». Комбинаторика . 19 (4): 453–472. дои : 10.1007/s004939970001 . S2CID 5724231 .
- ^ Конлон, Дэвид ; Фокс, Джейкоб ; Чжао, Юфэй (2014). «Теорема Грина – Тао: изложение». EMS-обзоры по математическим наукам . 1 (2): 249–282. arXiv : 1403.2957 . дои : 10.4171/EMSS/6 . МР 3285854 . S2CID 119301206 .