Расширяющий график

Разреженный граф с сильной связностью

В теории графов граф -расширитель — это разреженный граф , обладающий сильными связными свойствами, количественно определяемыми с помощью вершинного , рёберного или спектрального расширения. Конструкции расширителей породили исследования в области чистой и прикладной математики с несколькими приложениями к теории сложности , проектированию надёжных компьютерных сетей и теории кодов с исправлением ошибок . ^[1]

Определения

Интуитивно, граф-расширитель — это конечный неориентированный мультиграф , в котором каждое подмножество вершин, которое не «слишком велико», имеет «большую» границу . Различные формализации этих понятий приводят к различным понятиям расширителей: расширители рёбер , расширители вершин и расширители спектров , как определено ниже.

Несвязный граф не является расширителем, поскольку граница связного компонента пуста. Каждый связный граф является расширителем; однако различные связные графы имеют различные параметры расширения. Полный граф имеет наилучшее свойство расширения, но он имеет наибольшую возможную степень . Неформально, граф является хорошим расширителем, если он имеет низкую степень и высокие параметры расширения.

Расширение края

Расширение ребра (также изопериметрическое число или константа Чигера ) h ( G ) графа G на n вершинах определяется как

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

где ${\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\notin S\},}$

что также можно записать как ∂ S = E ( S , S ) с S  := V ( G ) \ S — дополнением S и

${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}$

ребра между подмножествами вершин A , B ⊆ V ( G ) .

В уравнении минимум находится по всем непустым множествам S, содержащим не более n ⁄ 2 вершин, а ∂ S — граница ребра S , т. е . множество ребер с ровно одной конечной точкой в ​​S. ^[2]

Интуитивно понятно,

${\displaystyle \min {|\partial S|}=\min E({S},{\overline {S}})}$

— это минимальное количество ребер, которые необходимо разрезать, чтобы разделить граф на две части. Расширение ребер нормализует эту концепцию, разделив ее на наименьшее количество вершин между двумя частями. Чтобы увидеть, как нормализация может кардинально изменить значение, рассмотрим следующий пример. Возьмем два полных графа с одинаковым количеством вершин n и добавим n ребер между двумя графами, соединив их вершины один к одному. Минимальный разрез будет равен n , но расширение ребер будет равно 1.

Обратите внимание, что в min | ∂ S | оптимизация может быть эквивалентно выполнена либо по 0 ≤ | S | ≤ n ⁄ 2 , либо по любому непустому подмножеству, поскольку . То же самое не относится к h ( G ) из-за нормализации по | S | . Если мы хотим записать h ( G ) с оптимизацией по всем непустым подмножествам, мы можем переписать его как ${\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}$

${\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {E({S},{\overline {S}})}{\min\{|S|,|{\overline {S}}|\}}}.}$

Расширение вершины

Изопериметрическое число вершин h _out ( G ) (также расширение или увеличение вершин ) графа G определяется как

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

где ∂ _out ( S ) — внешняя граница S , т. е. множество вершин в V ( G ) \ S с по крайней мере одним соседом в S . ^[3] В варианте этого определения (называемым расширением уникального соседа ) ∂ _out ( S ) заменяется множеством вершин в V с ровно одним соседом в S . ^[4]

Изопериметрическое число вершин h _в ( G ) графа G определяется как

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

где — внутренняя граница S , т. е. множество вершин в S, имеющих хотя бы одного соседа в V ( G ) \ S . ^[3] ${\displaystyle \partial _{\text{in}}(S)}$

Спектральное расширение

Когда G является d -регулярным , возможно линейное алгебраическое определение расширения, основанное на собственных значениях матрицы смежности A = A ( G ) графа G , где A _ij — число ребер между вершинами i и j . ^[5] Поскольку A симметричен , спектральная теорема подразумевает, что A имеет n вещественных собственных значений λ ₁ ≥ λ ₂ ≥ … ≥ λ _n . Известно, что все эти собственные значения находятся в [− d , d ] и, более конкретно, известно, что λ _n = − d тогда и только тогда, когда G является двудольным.

Более формально мы имеем в виду n -вершинный, d -регулярный граф с

${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$

как ( n , d , λ) -граф . Граница, заданная ( n , d , λ) -графом на λ _i для i ≠ 1 , полезна во многих контекстах, включая лемму о перемешивании экспандера .

Спектральное расширение может быть двусторонним , как выше, с , или оно может быть односторонним , с . Последнее является более слабым понятием, которое справедливо также для двудольных графов и по-прежнему полезно для многих приложений, таких как лемма Алона-Чунга. ^[6] ${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$ ${\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }$

Поскольку G является регулярным, равномерное распределение с u _i = 1 ⁄ n для всех i = 1, …, n является стационарным распределением G. То есть, мы имеем Au = du , а u является собственным вектором A с собственным значением λ ₁ = d , где d — степень вершин G. Спектральная щель G определяется как d − λ 2 , и она измеряет спектральное расширение графа G. _[ ⁷ ] ${\displaystyle u\in \mathbb {R} ^{n}}$

Если мы установим

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

Поскольку это наибольшее собственное значение, соответствующее собственному вектору, ортогональному u , его можно эквивалентно определить с помощью отношения Рэлея :

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

где

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

— 2-норма вектора . ${\displaystyle v\in \mathbb {R} ^{n}}$

Нормализованные версии этих определений также широко используются и более удобны для формулировки некоторых результатов. Здесь рассматривается матрица ⁠1/г⁠ A , которая является матрицей перехода Маркова графа G . Ее собственные значения находятся в диапазоне от −1 до 1. Для не обязательно регулярных графов спектр графа может быть определен аналогичным образом с использованием собственных значений матрицы Лапласа . Для ориентированных графов рассматриваются сингулярные значения матрицы смежности A , которые равны корням собственных значений симметричной матрицы A ^T A .

Взаимосвязи между различными свойствами расширения

Параметры расширения, определенные выше, связаны друг с другом. В частности, для любого d -регулярного графа G ,

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).}$

Следовательно, для графов постоянной степени расширение вершин и ребер качественно одинаково.

неравенства Чигера

Когда G является d -регулярным, то есть каждая вершина имеет степень d , существует связь между изопериметрической константой h ( G ) и зазором d − λ ₂ в спектре оператора смежности G . Согласно стандартной спектральной теории графов, тривиальное собственное значение оператора смежности d -регулярного графа равно λ ₁ = d , а первое нетривиальное собственное значение равно λ ₂ . Если G связен, то λ ₂ < d . Неравенство, полученное Додзюком ^[8] и независимо Алоном и Мильманом ^[9], утверждает, что ^[10]

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

На самом деле нижняя граница точна. Нижняя граница достигается в пределе для гиперкуба Q _n , где h ( G ) = 1 и d – λ ₂ = 2 . Верхняя граница (асимптотически) достигается для цикла, где h ( C _n ) = 4/ n = Θ(1/ n ) и d – λ ₂ = 2 – 2cos(2 / n ) ≈ (2 / n ) ² = Θ(1/ n ² ) ${\displaystyle \pi }$ ${\displaystyle \pi }$ . ^[1] Лучшая граница дана в ^[11] как

${\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}$

Эти неравенства тесно связаны с границей Чигера для цепей Маркова и могут рассматриваться как дискретная версия неравенства Чигера в римановой геометрии .

Аналогичные связи между вершинными изопериметрическими числами и спектральной щелью также были изучены: ^[12]

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

Асимптотически говоря, величины h ² ⁄ d , h _out и h _in ² ограничены сверху спектральной щелью O ( d – λ ₂ ) .

Конструкции

Существует четыре общие стратегии для явного построения семейств графов-расширителей. ^[13] Первая стратегия является алгебраической и теоретико-групповой, вторая стратегия является аналитической и использует аддитивную комбинаторику , третья стратегия является комбинаторной и использует зигзагообразные и связанные графовые произведения, а четвертая стратегия основана на подъемах. Нога Алон показал, что некоторые графы, построенные из конечных геометрий, являются самыми редкими примерами сильно расширяющихся графов. ^[14]

Маргулис–Габбер–Галил

Алгебраические конструкции, основанные на графах Кэли , известны для различных вариантов графов-расширителей. Следующая конструкция принадлежит Маргулису и была проанализирована Габбером и Галилом. ^[15] Для каждого натурального числа n рассматривается граф G _n с множеством вершин , где : Для каждой вершины ее восемь смежных вершин ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$ ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

Тогда справедливо следующее:

Теорема. Для всех n граф G _n имеет второе по величине собственное значение . ${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$

Графы Рамануджана

По теореме Алона и Боппаны все достаточно большие d -регулярные графы удовлетворяют , где λ ₂ — второе по величине собственное значение по абсолютной величине. ^[16] Как прямое следствие, мы знаем, что для каждого фиксированного d и существует только конечное число ( n , d , λ) -графов. Графы Рамануджана — это d -регулярные графы, для которых эта граница узка, удовлетворяя ^[17] ${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$ ${\displaystyle \lambda <2{\sqrt {d-1}}}$

${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}$

Следовательно, графы Рамануджана имеют асимптотически наименьшее возможное значение λ _2. Это делает их превосходными спектральными расширителями.

Любоцкий , Филлипс и Сарнак (1988), Маргулис (1988) и Моргенштерн (1994) показывают, как графы Рамануджана могут быть построены явно. ^[18]

В 1985 году Алон выдвинул гипотезу, что большинство d -регулярных графов на n вершинах для достаточно больших n являются почти рамануджановскими. ^[19] То есть, для ε > 0 они удовлетворяют

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$.

В 2003 году Джоэл Фридман доказал гипотезу и уточнил, что подразумевается под «большинством d -регулярных графов», показав, что случайные d -регулярные графы имеют для любого ε > 0 с вероятностью 1 – O ( n ^-τ ) , где ^{[20] [21]} ${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$

${\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}$

Более простое доказательство немного более слабого результата дал Пудер. ^{[22] [23] [24]}

Маркус , Шпильман и Шривастава ^[25] [ ^26] дали конструкцию двудольных графов Рамануджана, основанную на подъемах.

Зиг-Заг продукт

Рейнгольд , Вадхан и Вигдерсон ввели зигзагообразное произведение в 2003 году. ^[27] Грубо говоря, зигзагообразное произведение двух графов-расширителей дает граф с лишь немного худшим расширением. Поэтому зигзагообразное произведение также можно использовать для построения семейств графов-расширителей. Если G является ( n , d , λ ₁ ) -графом, а H является ( m , d , λ ₂ ) -графом, то зигзагообразное произведение G ◦ H является ( nm , d2 , φ (λ ₁ , λ ² )) -графом, где _φ обладает следующими свойствами.

1. Если λ ₁ < 1 и λ ₂ < 1 , то φ (λ ₁ , λ ₂ ) < 1 ;
2. φ (λ ₁ , λ ₂ ) ≤ λ ₁ + λ ₂ .

В частности, ^[27]

${\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}$

Обратите внимание, что свойство (1) подразумевает, что зигзагообразное произведение двух графов-расширителей также является графом-расширителем, поэтому зигзагообразные произведения можно использовать индуктивно для создания семейства графов-расширителей.

Интуитивно, построение зигзагообразного произведения можно представить следующим образом. Каждая вершина G раздувается до «облака» из m вершин, каждая из которых связана с различным ребром, соединенным с вершиной. Каждая вершина теперь помечена как ( v , k ) , где v относится к исходной вершине G , а k относится к k -му ребру v . Две вершины, ( v , k ) и ( w , l ), связаны, если возможно добраться из ( v , k ) в ( w , l ) с помощью следующей последовательности ходов.

1. Зиг - Перемещение из ( v , k ) в ( v , k' ) , используя ребро H.
2. Перепрыгните через облака, используя ребро k' в G, чтобы добраться до ( w , l' ) .
3. Zag - Перемещение из ( w , l' ) в ( w , l ), используя ребро H. ^[27]

Лифты

r -подъем графа формируется путем замены каждой вершины на r вершин, а каждого ребра на соответствие между соответствующими наборами вершин . Поднятый граф наследует собственные значения исходного графа и имеет некоторые дополнительные собственные значения. Билу и Линиал ^{[28] [29]} показали, что каждый d -регулярный граф имеет 2-подъем, в котором дополнительные собственные значения не превышают по величине. Они также показали, что если исходный граф является достаточно хорошим расширителем, то хороший 2-подъем может быть найден за полиномиальное время , тем самым давая эффективную конструкцию d -регулярных расширителей для каждого d . ${\displaystyle r}$ ${\displaystyle O({\sqrt {d\log ^{3}d}})}$

Билу и Линиал предположили, что границу можно улучшить до , что было бы оптимальным из-за границы Алона-Боппаны . Эта гипотеза была доказана в двудольной постановке Маркусом , Шпильманом и Шриваставой , ^{[25] [26]} которые использовали метод переплетения многочленов. В результате они получили альтернативную конструкцию двудольных графов Рамануджана . Первоначальное неконструктивное доказательство было превращено в алгоритм Майклом Б. Коэном. ^[30] Позже метод был обобщен на r -подъемы Холлом, Пудером и Савиным. ^[31] ${\displaystyle O({\sqrt {d\log ^{3}d}})}$ ${\displaystyle 2{\sqrt {d-1}}}$

Рандомизированные конструкции

Существует много результатов, которые показывают существование графов с хорошими свойствами расширения с помощью вероятностных аргументов. Фактически, существование расширителей было впервые доказано Пинскером ^[32], который показал, что для случайно выбранного n вершинного левого d регулярного двудольного графа , | N ( S ) | ≥ ( d – 2)| S | для всех подмножеств вершин | S | ≤ c _d n с высокой вероятностью, где c _d — константа, зависящая от d , которая равна O ( d ^-4 ) . Алон и Ройхман ^[33] показали, что для каждого 1 > ε > 0 существует некоторое c ( ε ) > 0 такое, что выполняется следующее: Для группы G порядка n рассмотрим граф Кэли на G с c ( ε ) log ₂ n случайно выбранными элементами из G . Тогда, в пределе n, стремящегося к бесконечности, полученный граф почти наверняка является ε -расширителем.

Применение и полезные свойства

Первоначальной мотивацией для экспандеров было построение экономичных надежных сетей (телефонных или компьютерных): экспандер с ограниченной степенью — это в точности асимптотически надежный граф с числом ребер, растущим линейно с размером (числом вершин) для всех подмножеств.

Графы-расширители нашли широкое применение в информатике , в проектировании алгоритмов , кодов исправления ошибок , экстракторов , псевдослучайных генераторов , сортировочных сетей (Ajtai, Komlós & Szemerédi (1983)) и надежных компьютерных сетей . Они также использовались в доказательствах многих важных результатов в теории вычислительной сложности , таких как SL  =  L (Reingold (2008)) и теорема PCP (Dinur (2007)). В криптографии графы-расширители используются для построения хэш-функций .

В обзоре 2006 года по графам-расширителям Хори, Линиал и Вигдерсон разделили изучение графов-расширителей на четыре категории: экстремальные задачи , типичное поведение, явные конструкции и алгоритмы. Экстремальные задачи фокусируются на ограничении параметров расширения, в то время как типичные проблемы поведения характеризуют, как параметры расширения распределены по случайным графам . Явные конструкции фокусируются на построении графов, которые оптимизируют определенные параметры, а алгоритмические вопросы изучают оценку и оценивание параметров.

Лемма о перемешивании экспандера

Лемма о перемешивании экспандера утверждает, что для ( n , d , λ) -графа для любых двух подмножеств вершин S , T ⊆ V , число ребер между S и T приблизительно равно ожидаемому в случайном d -регулярном графе. Приближение тем лучше, чем меньше λ . В случайном d -регулярном графе, а также в случайном графе Эрдёша–Реньи с вероятностью ребра d ⁄ n , мы ожидаем d ⁄ n • | S | • | T | ребер между S и T .

Более формально, пусть E ( S , T ) обозначает количество ребер между S и T . Если два множества не являются непересекающимися, ребра в их пересечении учитываются дважды, то есть,

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

Тогда лемма о перемешивании экспандера утверждает, что выполняется следующее неравенство:

${\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}$

Многие свойства ( n , d , λ) -графов являются следствиями лемм о перемешивании экспандеров, включая следующие. ^[1]

• Независимое множество графа — это подмножество вершин, в котором нет двух смежных вершин. В ( n , d , λ) -графе независимое множество имеет размер не более λ n ⁄ d .
• Хроматическое число графа G , χ( G ) , — это минимальное количество цветов, необходимое для того, чтобы смежные вершины имели разные цвета. Хоффман показал, что d ⁄ λ ≤ χ( G ) , ^[34] в то время как Алон, Кривелевич и Судаков показали, что если d < 2 n ⁄ 3 , то ^[35]

  ${\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}$

• Диаметр графа — это максимальное расстояние между двумя вершинами, где расстояние между двумя вершинами определяется как кратчайший путь между ними. Чанг показал, что диаметр ( n , d , λ) -графа не превышает ^[36]

  ${\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}$

Выборка для экспандерного обхода

Граница Чернова утверждает, что при выборке множества независимых выборок из случайной величины в диапазоне [−1, 1] с высокой вероятностью среднее значение наших выборок близко к ожиданию случайной величины. Лемма выборки с использованием экспандерного блуждания, принадлежащая Ajtai, Komlós & Szemerédi (1987) и Gillman (1998), утверждает, что это также справедливо при выборке из блуждания по графу экспандера. Это особенно полезно в теории дерандомизации , поскольку выборка в соответствии с экспандерным блужданием использует гораздо меньше случайных битов, чем независимая выборка.

Сеть сортировки АКС и примерные халверы

Сортировочные сети берут набор входов и выполняют ряд параллельных шагов для сортировки входов. Параллельный шаг состоит из выполнения любого количества непересекающихся сравнений и потенциальной перестановки пар сравниваемых входов. Глубина сети задается количеством параллельных шагов, которые она выполняет. Графы-расширители играют важную роль в сортировочной сети AKS, которая достигает глубины O (log n ) . Хотя это асимптотически лучшая известная глубина для сортировочной сети, зависимость от расширителей делает константную границу слишком большой для практического использования.

В сортировочной сети AKS графы-расширители используются для построения ограниченных глубин ε -половинок. ε -половинка принимает в качестве входных данных перестановку длины n (1, …, n ) и делит входные данные пополам на два непересекающихся множества A и B таким образом, что для каждого целого числа k ≤ n ⁄ 2 не более εk из k наименьших входных данных находятся в B и не более εk из k наибольших входных данных находятся в A . Множества A и B являются ε -половинкой.

Следуя Ajtai, Komlós & Szemerédi (1983), глубина d ε -halver может быть построена следующим образом. Возьмем n вершинный, степень d двудольный расширитель с частями X и Y одинакового размера, такой, что каждое подмножество вершин размера не более εn имеет по крайней мере ⁠1 – ε/ε⁠ соседи.

Вершины графа можно рассматривать как регистры, содержащие входы, а ребра можно рассматривать как провода, сравнивающие входы двух регистров. В начале произвольно поместите половину входов в X , а половину входов в Y и разложите ребра на d идеальных соответствий. Цель состоит в том, чтобы в итоге X примерно содержал меньшую половину входов, а Y содержал примерно большую половину входов. Чтобы добиться этого, последовательно обрабатывайте каждое соответствие, сравнивая регистры, объединенные в пары ребрами этого соответствия, и исправляйте любые входы, которые находятся не в порядке. В частности, для каждого ребра соответствия, если больший вход находится в регистре в X , а меньший вход находится в регистре в Y , то поменяйте местами два входа так, чтобы меньший находился в X , а больший — в Y. Очевидно, что этот процесс состоит из d параллельных шагов.

После всех d раундов возьмем A как набор входов в регистрах в X и B как набор входов в регистрах в Y, чтобы получить ε -деление пополам. Чтобы увидеть это, обратите внимание, что если регистр u в X и v в Y соединены ребром uv , то после обработки сопоставления с этим ребром вход в u меньше, чем у v . Более того, это свойство остается верным на протяжении всего оставшегося процесса. Теперь предположим, что для некоторого k ≤ n ⁄ 2 более εk входов (1, …, k ) находятся в B . Тогда по свойствам расширения графа регистры этих входов в Y соединены по крайней мере с ⁠1 – ε/ε⁠ k регистров в X. В общей сложности это составляет более k регистров, поэтому должен быть некоторый регистр A в X, соединенный с некоторым регистром B в Y таким образом, что конечный вход A не находится в (1, …, k ) , в то время как конечный вход B находится. Однако это нарушает предыдущее свойство, и, таким образом, выходные наборы A и B должны быть ε -пополам.

Смотрите также

• Алгебраическая связность
• Зигзагообразный продукт
• Сверхсильное приближение
• Теория спектральных графов

Примечания

1. Hoory, Линиал и Вигдерсон (2006)
2. Определение 2.1 в Hoory, Linial & Wigderson (2006)
3. Бобков, Удре и Тетали (2000)
4. Алон и Капальбо (2002)
5. см. Раздел 2.3 в Hoory, Linial & Wigderson (2006)
6. Н. Алон и Ф. Р. К. Чунг, Явное построение толерантных сетей линейного размера. Дискретная математика, т. 72, стр. 15-19, 1988.
7. Это определение спектральной щели взято из раздела 2.3 в Hoory, Linial & Wigderson (2006)
8. Додзюк 1984.
9. Алон и Спенсер 2011.
10. Теорема 2.4 в Hoory, Linial & Wigderson (2006)
11. Б. Мохар. Изопериметрические числа графов. J. Combin. Theory Ser. B, 47(3):274–291, 1989.
12. См. теорему 1 и стр. 156, л. 1 в Bobkov, Houdré & Tetali (2000). Обратите внимание, что λ ₂ там соответствует 2( d − λ ₂ ) текущей статьи (см. стр. 153, л. 5)
13. см., например, Yehudayoff (2012)
14. Алон, Нога (1986). «Собственные значения, геометрические экспандеры, сортировка раундами и теория Рамсея». Combinatorica . 6 (3): 207–219. CiteSeerX  10.1.1.300.5945 . doi :10.1007/BF02579382. S2CID  8666466.
15. см., например, стр. 9 Goldreich (2011)
16. Теорема 2.7 Хури, Линиала и Вигдерсона (2006)
17. Определение 5.11 из Hoory, Linial & Wigderson (2006)
18. Теорема 5.12 Хури, Линиала и Вигдерсона (2006)
19. Алон, Нога (1986-06-01). «Собственные значения и расширители». Combinatorica . 6 (2): 83–96. doi :10.1007/BF02579166. ISSN  1439-6912. S2CID  41083612.
20. Фридман, Джоэл (2004-05-05). «Доказательство второй гипотезы Алона о собственных значениях и связанные с ней проблемы». arXiv : cs/0405020 .
21. Теорема 7.10 Хури, Линиала и Вигдерсона (2006)
22. Puder, Doron (2015-08-21). «Расширение случайных графов: новые доказательства, новые результаты». Inventiones Mathematicae . 201 (3): 845–908. arXiv : 1212.5216 . Bibcode : 2015InMat.201..845P. doi : 10.1007/s00222-014-0560-x. S2CID  253743928.
23. Puder, Doron (2015). «Расширение случайных графов: новые доказательства, новые результаты». Inventiones Mathematicae . 201 (3): 845–908. arXiv : 1212.5216 . Bibcode : 2015InMat.201..845P. doi : 10.1007/s00222-014-0560-x. ISSN  0020-9910. S2CID  16411939.
24. Фридман, Джоэл; Пудер, Дорон (2023). «Заметка о методе трассировки для случайных регулярных графов». Israel Journal of Mathematics . 256 : 269–282. arXiv : 2006.13605 . doi : 10.1007/s11856-023-2497-5. S2CID  220042379.
25. Адам Маркус ; Дэниел Шпильман ; Нихил Шривастава (2013). Переплетение семейств I: Двудольные графы Рамануджана всех степеней (PDF) . Основы компьютерной науки (FOCS), 54-й ежегодный симпозиум IEEE 2013.
26. Адам Маркус ; Дэниел Шпильман ; Нихил Шривастава (2015). Переплетение семейств IV: Двудольные графы Рамануджана всех размеров (PDF) . Основы компьютерной науки (FOCS), 56-й ежегодный симпозиум IEEE 2015 года.
27. Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Волны энтропии, произведение зигзагообразных графов и новые экспандеры и экстракторы постоянной степени". Труды 41-го ежегодного симпозиума по основам компьютерной науки . IEEE Comput. Soc. стр. 3–13. doi :10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID  420651.
28. Билу, Йонатан; Линиал, Натан (8 апреля 2004 г.). «Построение графов-расширителей с помощью 2-подъемов и несоответствия в зависимости от спектрального разрыва». arXiv : математика/0312022 .
29. Билу, Йонатан; Линиал, Натан (2006). «Подъемы, расхождение и почти оптимальный спектральный зазор». Combinatorica . 26 (5): 495–519. doi :10.1007/s00493-006-0029-7. ISSN  0209-9683. S2CID  14422668.
30. Майкл Б. Коэн (2016). Графы Рамануджана за полиномиальное время . Основы компьютерной науки (FOCS), 57-й ежегодный симпозиум IEEE 2016 года. arXiv : 1604.03544 . doi : 10.1109/FOCS.2016.37.
31. Холл, Крис; Пудер, Дорон; Савин, Уильям Ф. (2018). «Покрытия Рамануджана графов». Успехи математики . 323 : 367–410. arXiv : 1506.02335 . doi : 10.1016/j.aim.2017.10.042.
32. Пинксер, М. (1973). «О сложности концентратора». Журнал SIAM по вычислениям . SIAM. CiteSeerX 10.1.1.393.1430 . 
33. Алон, Н.; Ройхман, И. (1994). «Случайные графы Кэли и экспандеры». Случайные структуры и алгоритмы . 5 (2). Онлайн-библиотека Wiley: 271–284. doi :10.1002/rsa.3240050203.
34. Хоффман, А. Дж.; Хоус, Леонард (1970). «О собственных значениях и раскрасках графов, Ii». Анналы Нью-Йоркской академии наук . 175 (1): 238–242. Bibcode : 1970NYASA.175..238H. doi : 10.1111/j.1749-6632.1970.tb56474.x. ISSN  1749-6632. S2CID  85243045.
35. Алон, Нога ; Кривелевич, Майкл ; Судаков, Бенни (1999-09-01). «Раскраска графов с разреженными окрестностями». Журнал комбинаторной теории . Серия B. 77 (1): 73–82. doi : 10.1006/jctb.1999.1910 . ISSN  0095-8956.
36. Chung, FRK (1989). «Диаметры и собственные значения». Журнал Американского математического общества . 2 (2): 187–196. doi : 10.1090/S0894-0347-1989-0965008-X . ISSN  0894-0347.

Ссылки

Учебники и обзоры

• Алон, Н .; Спенсер, Джоэл Х. (2011). "9.2. Собственные значения и экспандеры". Вероятностный метод (3-е изд.). John Wiley & Sons.
• Chung, Fan RK (1997), Теория спектральных графов , CBMS Regional Conference Series in Mathematics, т. 92, Американское математическое общество , ISBN 978-0-8218-0315-8
• Давидофф, Джулиана; Сарнак, Питер; Валетт, Ален (2003), Элементарная теория чисел, теория групп и графы Рамануджана , тексты для студентов LMS, т. 55, Cambridge University Press , ISBN 978-0-521-53143-6
• Hoory, Shlomo; Linial, Nathan ; Wigderson, Avi (2006), "Расширительные графы и их приложения" (PDF) , Bulletin of the American Mathematical Society , New Series, 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8
• Кребс, Майк; Шахин, Энтони (2011), Семейства экспандеров и графы Кэли: руководство для начинающих , Oxford University Press, ISBN 978-0-19-976711-3

Научные статьи

• Ajtai, M. ; Komlós, J. ; Szemerédi, E. (1983), "Сеть сортировки O(n log n)", Труды 15-го ежегодного симпозиума ACM по теории вычислений , стр. 1–9, doi :10.1145/800061.808726, ISBN 978-0-89791-099-6, S2CID  15311122
• Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), «Детерминированное моделирование в LOGSPACE», Труды 19-го ежегодного симпозиума ACM по теории вычислений , ACM, стр. 132–140, doi : 10.1145/28395.28410 , ISBN 978-0-89791-221-1, S2CID  15323404
• Алон, Н.; Капальбо, М. (2002), "Явные расширители уникального соседа", 43-й ежегодный симпозиум IEEE по основам компьютерной науки, 2002. Труды , стр. 73, CiteSeerX  10.1.1.103.967 , doi :10.1109/SFCS.2002.1181884, ISBN 978-0-7695-1822-0, S2CID  6364755
• Бобков С.; Удре, К.; Тетали, П. (2000), «λ _∞ , вершинная изопериметрия и концентрация», Combinatorica , 20 (2): 153–172, doi : 10.1007/s004930070018, S2CID  1173532.
• Динур, Ирит (2007), «Теорема PCP путем усиления разрыва» (PDF) , Journal of the ACM , 54 (3): 12–es, CiteSeerX  10.1.1.103.2644 , doi : 10.1145/1236457.1236459, S2CID  53244523.
• Додзюк, Йозеф (1984), «Разностные уравнения, изопериметрическое неравенство и скоротечность некоторых случайных блужданий», Trans. Amer. Math. Soc. , 284 (2): 787–794, doi : 10.2307/1999107 , JSTOR  1999107.
• Гиллман, Д. (1998), «Граница Чернова для случайных блужданий на графах-расширителях», SIAM Journal on Computing , 27 (4): 1203–1220, doi :10.1137/S0097539794268765
• Goldreich, Oded (2011), "Основные факты о графах-расширителях", Исследования по сложности и криптографии. Разное о взаимодействии случайности и вычислений (PDF) , Lecture Notes in Computer Science (т. 6650), т. 6650, стр. 451–464, CiteSeerX  10.1.1.231.1388 , doi :10.1007/978-3-642-22670-0_30, ISBN 978-3-642-22669-4
• Рейнгольд, Омер (2008), «Ненаправленная связность в лог-пространстве», Журнал ACM , 55 (4): 1–24, doi :10.1145/1391289.1391291, S2CID  207168478
• Йехудайофф, Амир (2012), «Доказательство расширения в три этапа», ACM SIGACT News , 43 (3): 67–84, doi : 10.1145/2421096.2421115, S2CID  18098370

Последние заявки

• Хартнетт, Кевин (2018), «Универсальный метод сортировки сложной информации», Quanta Magazine (опубликовано 13 августа 2018 г.)

Внешние ссылки

• Краткое введение в Notices of the American Mathematical Society
• Вступительная статья Майкла Нильсена Архивировано 17 августа 2016 г. на Wayback Machine
• Конспект лекций по курсу эспандеров (Нати Линиал и Ави Вигдерсон)
• Конспект лекций по курсу эспандеров (Прахлад Харша)
• Определение и применение спектральной щели