Оглавление
- 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 Полный текст статьи:
- 2 Псевдослучайный график – Arc.Ask3.Ru
Псевдослучайный граф
-
Определение псевдослучайности графов
- Граф называется псевдослучайным, если он подчиняется определенным свойствам, которым случайные графы подчиняются с высокой вероятностью.
- Конкретного определения псевдослучайности не существует, но есть много разумных характеристик.
-
Условие беспорядочности
- Граф 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, λ)-построение граф имеет собственные значения, удовлетворяющие условию λ ≤ 2d-1.
- Случайный d-обычный граф на n вершин является (n, d, λ) для λ = 2d-1 + o(1).
- Графы с λ ≤ 2d-1 называются графами Рамануджана и имеют нерешенные проблемы.
-
Влияние λ на свойства графов
- Размер λ влияет на расхождения в плотности краев подмножества.
- При d ≤ n/2, вершинная связность κ(G) удовлетворяет κ(G) ≥ d-36λ^2/d.
- При λ ≤ d-2, G является d-соединенным по краям.
- При четном n, G содержит идеальное сочетание.
- Максимальный срез G не превышает n(d+λ)/4.
- Самое большое независимое подмножество из U ⊂ V(G) имеет размер не менее n/2(d-λ) ln(|U|(d-λ)/n(λ+1)+1).
- Хроматическое число G не превышает 6(d-λ) ln(d+1/λ+1).
-
Связь с теоремой Грина–Тао
- Псевдослучайные графы играют важную роль в доказательстве теоремы Грина–Тао.
- Теорема доказывается путем переноса теоремы Семереди в разреженную настройку.
- Переход к разреженным множествам требует псевдослучайности, что показано для псевдопростых чисел.