Оглавление
- 1 Псевдослучайный граф
- 1.1 Определение псевдослучайности графов
- 1.2 Условие беспорядочности
- 1.3 Соответствие местным условиям
- 1.4 Теорема Чанга–Грэма–Уилсона
- 1.5 Связи с регулярностью графов
- 1.6 Редкая псевдослучайность
- 1.7 Полные графы и их собственные значения
- 1.8 (n, d, λ)-построение графиков
- 1.9 Графы Рамануджана
- 1.10 Влияние λ на теоретико-графовые величины
- 1.11 Максимальный срез и независимое подмножество
- 1.12 Связи с теоремой Грина–Тао
- 1.13 Полный текст статьи:
- 2 Псевдослучайный график
Псевдослучайный граф
-
Определение псевдослучайности графов
- Граф называется псевдослучайным, если он подчиняется определенным свойствам, которым случайные графы подчиняются с высокой вероятностью.
- Конкретного определения псевдослучайности не существует, но есть много разумных характеристик.
-
Условие беспорядочности
- Граф G называется (p, α)-перемешанным, если для каждого подмножества U из множества вершин V, e(U) ≤ p|U|α.
- Случайный граф Эрдеша–Реньи почти наверняка (p, O(np))-перемешан.
-
Соответствие местным условиям
- Томасон показал, что условие беспорядочности подразумевает более простое условие, зависящее от кодового дерева двух вершин.
- Граф G на n вершин с минимальной степенью np и кодег(u, v) ≤ np2 + ℓ для всех u и v является (p, (p + ℓ)n)-перемешанным.
-
Теорема Чанга–Грэма–Уилсона
- Чанг, Грэм и Уилсон рассмотрели несколько более слабых условий псевдослучайности.
- Граф G на n вершин с плотностью ребер p и ε > 0 может удовлетворять условиям несоответствия, расхождения в отдельных наборах, подсчета подграфов, подсчета за 4 цикла, кодового дерева и ограничения по собственному значению.
- Все эти условия могут быть представлены в виде последовательности графиков {Gn}, где Gn включает n вершин с (p + o(1))n2 ребер.
- Теорема Чанга–Грэма–Уилсона утверждает, что многие из этих условий эквивалентны, вплоть до полиномиальных изменений в ε.
-
Связи с регулярностью графов
- Концепция графов, действующих как случайные, связана с регулярностью графов.
- Граф удовлетворяет условиям слабой псевдослучайности, если он обладает разбиением Семереди, в котором почти все плотности близки к плотности ребер всего графа.
-
Редкая псевдослучайность
- Теорема Чанга–Грэма–Уилсона не выполняется для последовательностей графов с плотностью ребер, приближающейся к 0.
- Рассматриваются разреженные аналоги условий ограничения расхождения и собственных значений.
-
Полные графы и их собственные значения
- Полный граф имеет два собственных значения, равных d, но, скорее всего, удовлетворяет свойству несоответствия.
- Незначительные отклонения от условий расхождения и собственных значений для d-обычных графиков Кэли эквивалентны линейному масштабированию в ε.
-
(n, d, λ)-построение графиков
- (n, d, λ)-построение график: собственные значения матрицы смежности G равны d = λ1 ≥ λ2 ≥ … ≥ λn, максимум (|λ2|, |λn|) ≤ λ.
- Связь Алон-Боппана: максимум (|λ2|, |λn|) ≥ 2√d-1 – o(1).
- Случайный d-обычный график на n вершин: λ = 2√d-1 + o(1).
-
Графы Рамануджана
- Графы с λ ≤ 2√d-1 называются графами Рамануджана.
- Существуют нерешенные проблемы, связанные с их существованием и распространенностью.
-
Влияние λ на теоретико-графовые величины
- Размер λ влияет на расхождения в плотности краев подмножества.
- Примеры: κ(G) ≥ d – 36λ2/d при d ≤ n/2; G является d-соединенным по краям при λ ≤ d-2; G содержит идеальное сочетание при n четном.
-
Максимальный срез и независимое подмножество
- Максимальный срез G: n(d + λ)/4.
- Самое большое независимое подмножество U ⊂ V(G): n/2(d – λ) ln(|U|(d – λ)n(λ + 1) + 1).
- Хроматическое число G: 6(d – λ) ln(d + 1/λ + 1).
-
Связи с теоремой Грина–Тао
- Псевдослучайные графы играют важную роль в доказательстве теоремы Грина–Тао.
- Теорема доказывается путем переноса теоремы Семереди в разреженную настройку.
- Переход к разреженным множествам требует псевдослучайности, что показано для псевдопростых чисел.