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

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

Определения

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

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

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

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

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

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

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

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

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

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

Интуитивно,

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

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

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

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

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

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

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

где ∂out _в ( S ) — внешняя граница , S множество вершин в V ( G )\ S с хотя бы одним соседом S. т.е. В варианте этого определения (так называемом уникальных соседей ) ∂out _{заменяется} ( S ) набором вершин в V с ровно одним соседом в S. расширении

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

$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 . Неравенство Додзюка и независимо Алон и Мильман заявляет, что

${\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 $\pi$/ п ) ≈ (2 $\pi$/ н ) ² = Θ(1/ n ² ) . Лучшая оценка дана в как

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

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

Подобные связи между изопериметрическими числами вершин и спектральной щелью также были изучены:

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

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

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

Конструкции

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

Маргулис-Габбер-Галиль

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

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

Тогда имеет место следующее:

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

Графики Рамануджана

Основная статья: граф Рамануджана

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

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

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

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

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

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

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

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

Более простое доказательство несколько более слабого результата было дано Пудером.

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

Зигзагообразный продукт

Основная статья: Зигзагообразное изделие

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

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

Конкретно,

$\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. Заг — Переместитесь из ( w , l' ) в ( w , l ), ребро H. используя

Лифты

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

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

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

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

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

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

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

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

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

Основная статья: Лемма о смешивании экспандера

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

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

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

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

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

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

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

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

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

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

Выборка обхода Expander

Основная статья: Выборка обхода Expander

Граница Чернова утверждает, что при выборке множества независимых выборок из случайной величины в диапазоне [-1, 1] с высокой вероятностью среднее значение наших выборок близко к математическому ожиданию случайной величины. Лемма о выборке обхода расширителя, предложенная Айтаи, Комлосом и Семереди (1987) и Гиллманом (1998) , утверждает, что это также справедливо при выборке из обхода графа расширителя. Это особенно полезно в теории дерандомизации , поскольку выборка в соответствии с экспандерным обходом использует гораздо меньше случайных битов, чем независимая выборка.

Сортировочная сеть АКС

Основная статья: Сортировочная сеть

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

В сортировочной сети AKS графы расширения используются для построения ε -половинок ограниченной глубины. ε A длины n -халвер принимает в качестве входных данных перестановку (1, …, n ) и делит входные данные пополам на два непересекающихся набора такие и 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 связаны как минимум с – ε / ε k регистрируется в X. 1 В общей сложности это более чем k регистров, поэтому должен быть какой-то регистр A в X, соединенный с некоторым регистром B в Y, так что последний вход A не находится в (1, …, k ) , а последний вход B есть. Однако это нарушает предыдущее свойство, и, следовательно, выходные множества A и B должны быть ε -половинками.

См. также

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

Ссылки

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

• Алон, Н. ; Спенсер, Джоэл Х. (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 , номер 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) , Журнал 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 г.)

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

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