Jump to content

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

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

Псевдослучайные свойства впервые были официально рассмотрены Эндрю Томасоном в 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] Затем показано, что подходящее надмножество простых чисел, называемое псевдопростыми числами, в котором простые числа плотны, подчиняется этим условиям псевдослучайности, что завершает доказательство.

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