Расширяемый график

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

В теории графов граф -расширитель — это разреженный граф , обладающий сильными свойствами связности , количественно определяемыми с помощью вершинного , реберного или спектрального расширения. Конструкции расширителей породили исследования в области чистой и прикладной математики с несколькими приложениями к теории сложности , проектированию надежных компьютерных сетей и теории кодов, исправляющих ошибки . ^[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.

Обратите внимание, что через мин | ∂ С | , оптимизация может быть эквивалентно выполнена либо при 0 ≤ | С | ≤ n ⁄ 2 или над любым непустым подмножеством, поскольку . Этого нельзя сказать о h ( G ) из-за нормализации | С | . Если мы хотим записать 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}}|\}}}.}$

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

Изопериметрический номер вершины _hout ( 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 , где Aij _— количество ребер между вершинами 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 − λ ₂ и измеряет спектральное расширение графа G . ^[7] ${\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 )^2 знак равно Θ(1/ п ² ) ${\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}}.}$

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

Любоцкий , Филлипс и Сарнак (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 , m , λ ₁ ) -граф, а H — ( m , d , λ ₁ ) -граф, то зигзагообразное произведение G ◦ H — это ( nm , d ² , φ (λ ₁₎ , λ ₂ )) -граф, где φ обладает следующими свойствами.

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

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

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

Экспандерные графы нашли широкое применение в информатике , при разработке алгоритмов , кодов с исправлением ошибок , экстракторов , генераторов псевдослучайных чисел , сортировочных сетей (Айтай, Комлос и Семереди (1983)) и надежных компьютерных сетей . Они также использовались в доказательствах многих важных результатов теории сложности вычислений , таких как SL  =  L (Рейнгольд (2008)) и теорема PCP (Динур (2007)). В криптографии расширительные графы используются для построения хеш-функций .

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

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

Лемма о смешивании расширителя утверждает, что для ( n , d , λ) -графа для любых двух подмножеств вершин S , T ⊆ V количество ребер между S и T примерно соответствует тому, что можно было бы ожидать в случайном d - обычный график. Приближение тем лучше, чем меньше λ . В случайном d -регулярном графе, а также в случайном графе Эрдеша–Реньи с вероятностью ребра d ⁄ n мы ожидаем, что d ⁄ n • | С | • | Т | края между 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] с высокой вероятностью среднее значение наших выборок близко к математическому ожиданию случайной величины. Лемма о выборке обхода расширителя, предложенная Айтаем, Комлосом и Семереди (1987) и Гиллманом (1998), утверждает, что это также справедливо при выборке из обхода графа расширителя. Это особенно полезно в теории дерандомизации , поскольку выборка в соответствии с экспандерным обходом использует гораздо меньше случайных битов, чем независимая выборка.

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

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

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

Следуя Ajtai, Komlos & Szemeredi (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 в книге Хори, Линиал и Вигдерсон (2006)
6. Н. Алон и Ф. Р. Чанг, Явное построение толерантных сетей линейного размера. Дискретная математика., вып. 72, стр. 15–19, 1988.
7. Это определение спектральной щели взято из раздела 2.3 в Hoory, Linial & Wigderson (2006).
8. Додзюк 1984.
9. Алон и Спенсер 2011.
10. Теорема 2.4 в книге Хори, Линиала и Вигдерсона (2006).
11. Б. Мохар. Изопериметрические числа графов. Дж. Комбин. Теория Сер. Б, 47(3):274–291, 1989.
12. См. теорему 1 и стр. 156, л.1 в книге Бобкова, Удре и Тетали (2000). Заметим, что λ ₂ соответствует 2( d − λ ₂ ) настоящей статьи (см. с.153, л.5)
13. см., например, Yehudayoff (2012).
14. Алон, Нога (1986). «Собственные значения, геометрические расширители, раундовая сортировка и теория Рэмси». Комбинаторика . 6 (3): 207–219. CiteSeerX  10.1.1.300.5945 . дои : 10.1007/BF02579382. S2CID  8666466.
15. см., например, стр.9 Goldreich (2011).
16. Теорема 2.7 Хори, Линиала и Вигдерсона (2006).
17. Определение 5.11 Хори, Линиала и Вигдерсона (2006).
18. Теорема 5.12 Хори, Линиала и Вигдерсона (2006).
19. Алон, Нога (1 июня 1986 г.). «Собственные значения и расширители». Комбинаторика . 6 (2): 83–96. дои : 10.1007/BF02579166. ISSN  1439-6912. S2CID  41083612.
20. Фридман, Джоэл (5 мая 2004 г.). «Доказательство второй гипотезы о собственных значениях Алона и связанных с ней проблем». arXiv : cs/0405020 .
21. Теорема 7.10 Хори, Линиала и Вигдерсона (2006).
22. Пудер, Дорон (21 августа 2015 г.). «Разложение случайных графов: Новые доказательства, новые результаты». Математические изобретения . 201 (3): 845–908. arXiv : 1212.5216 . Бибкод : 2015InMat.201..845P. doi : 10.1007/s00222-014-0560-x. S2CID  253743928.
23. Пудер, Дорон (2015). «Разложение случайных графов: новые доказательства, новые результаты». Математические изобретения . 201 (3): 845–908. arXiv : 1212.5216 . Бибкод : 2015InMat.201..845P. doi : 10.1007/s00222-014-0560-x. ISSN  0020-9910. S2CID  16411939.
24. Фридман, Джоэл; Пудер, Дорон (2023). «Заметка о методе трассировки случайных регулярных графов». Израильский математический журнал . 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. Рейнгольд, О.; Вадхан, С.; Вигдерсон, А. (2000). «Волны энтропии, произведение зигзагообразного графа и новые расширители и экстракторы постоянной степени». Материалы 41-го ежегодного симпозиума по основам информатики . IEEE-компьютер. Соц. стр. 3–13. дои : 10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID  420651.
28. Билу, Йонатан; Линиал, Натан (8 апреля 2004 г.). «Построение графов-расширителей с помощью 2-подъемов и несоответствия в зависимости от спектрального разрыва». arXiv : математика/0312022 .
29. Билу, Йонатан; Линиал, Натан (2006). «Подъемы, несоответствие и почти оптимальный спектральный разрыв». Комбинаторика . 26 (5): 495–519. дои : 10.1007/s00493-006-0029-7. ISSN  0209-9683. S2CID  14422668.
30. Майкл Б. Коэн (2016). Графы Рамануджана за полиномиальное время . Основы компьютерных наук (FOCS), 57-й ежегодный симпозиум IEEE, 2016 г. arXiv : 1604.03544 . дои : 10.1109/FOCS.2016.37.
31. Холл, Крис; Пудер, Дорон; Савин, Уильям Ф. (2018). «Рамануджановские покрытия графов». Достижения в математике . 323 : 367–410. arXiv : 1506.02335 . дои : 10.1016/j.aim.2017.10.042.
32. Пинксер, М. (1973). «О сложности концентратора». SIAM Journal по вычислительной технике . СИАМ. CiteSeerX 10.1.1.393.1430 . 
33. Алон, Н.; Ройхман, Ю. (1994). «Случайные графы Кэли и расширители». Случайные структуры и алгоритмы . Интернет-библиотека Уайли. 5 (2): 271–284. дои : 10.1002/rsa.3240050203.
34. Хоффман, AJ; Хоуз, Леонард (1970). «О собственных значениях и раскрасках графов, II». Анналы Нью-Йоркской академии наук . 175 (1): 238–242. Бибкод : 1970NYASA.175..238H. doi :10.1111/j.1749-6632.1970.tb56474.x. ISSN  1749-6632. S2CID  85243045.
35. Алон, Нога ; Кривелевич Михаил ; Судаков, Бенни (1 сентября 1999 г.). «Раскраска графов с разреженными окрестностями». Журнал комбинаторной теории . Серия Б. 77 (1): 73–82. дои : 10.1006/jctb.1999.1910 . ISSN  0095-8956.
36. Чунг, ФРК (1989). «Диаметры и собственные значения». Журнал Американского математического общества . 2 (2): 187–196. дои : 10.1090/S0894-0347-1989-0965008-X . ISSN  0894-0347.

Рекомендации

Учебники и опросы

• Алон, Н. ; Спенсер, Джоэл Х. (2011). «9.2. Собственные значения и расширители». Вероятностный метод (3-е изд.). Джон Уайли и сыновья.
• Чунг, Фан Р.К. (1997), Теория спектральных графов , Серия региональных конференций CBMS по математике, том. 92, Американское математическое общество , ISBN. 978-0-8218-0315-8
• Давидофф, Гильяна; Сарнак, Питер; Валетт, Ален (2003), Элементарная теория чисел, теория групп и графы Рамануджана , Учебники для студентов LMS, том. 55, Издательство Кембриджского университета , ISBN 978-0-521-53143-6
• Хори, Шломо; Линиал, Натан ; Вигдерсон, Ави (2006), «Расширяющие графики и их приложения» (PDF) , Бюллетень Американского математического общества , Новая серия, 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8
• Кребс, Майк; Шахин, Энтони (2011), Семейства Expander и графы Кэли: руководство для начинающих , Oxford University Press, ISBN 978-0-19-976711-3

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

• Аджтай, М. ; Комлос, Дж .; Семереди, Э. (1983), «Сортировочная сеть O (n log n)», Труды 15-го ежегодного симпозиума ACM по теории вычислений , стр. 1–9, doi : 10.1145/800061.808726, ISBN 978-0-89791-099-6, S2CID  15311122
• Аджтай, М.; Комлос, Дж.; Семереди, Э. (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 , номер документа : 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), «Разностные уравнения, изопериметрическое неравенство и быстротечность некоторых случайных блужданий», Пер. амер. Математика. Соц. , 284 (2): 787–794, номер документа : 10.2307/1999107 , JSTOR  1999107..
• Гиллман, Д. (1998), «Оценка Чернова для случайных блужданий по экспандерным графам», SIAM Journal on Computing , 27 (4): 1203–1220, doi : 10.1137/S0097539794268765
• Гольдрейх, Одед (2011), «Основные факты о расширительных графах», Исследования по сложности и криптографии. Разное о взаимодействии случайности и вычислений (PDF) , Конспекты лекций по информатике (том 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 (опубликовано 13 августа 2018 г.)

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

• Краткое введение в «Извещениях Американского математического общества».
• Вступительная статья Майкла Нильсена
• Конспекты лекций из курса по эспандерам (автор: Нати Линиал и Ави Вигдерсон)
• Конспекты лекций из курса по экспандерам (Прахлад Харша)
• Определение и применение спектральной щели