График расширения

В комбинаторной математике граф - расширитель — это разреженный граф , обладающий сильными свойствами связности , количественно определяемый с использованием вершинного , реберного или спектрального расширения. Экспандерные конструкции породили исследования в области чистой и прикладной математики с несколькими приложениями к теории сложности , проектированию надежных компьютерных сетей и теории кодов, исправляющих ошибки . ^[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 \ in V (G) \ setminus S \}}$${\ Displaystyle \ парциальное S = E (S, {\ overline {S}})}$${\ displaystyle {\ overline {S}}: = V (G) \ setminus S}$${\ Displaystyle S}$${\ displaystyle E (A, B) = \ {\ {u, v \} \ in E (G) \: \ u \ in A, v \ in B \}}$${\displaystyle A,B\subseteq V(G)}$

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

Интуитивно,

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

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

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

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

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

Изопериметрический номер вершины (также расширение или увеличение вершины ) графа G определяется как${\displaystyle h_{\text{out}}(G)}$

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

где — внешняя граница S , т . е. множество вершин в , имеющих хотя бы одного соседа в S . ^[3] В варианте этого определения (называемом расширением уникальных соседей ) заменяется набором вершин в V ровно с одним соседом в S. ^[4]${\displaystyle \partial _{\text{out}}(S)}$${\displaystyle V(G)\setminus S}$${\displaystyle \partial _{\text{out}}(S)}$

Изопериметрический номер вершины графа G определяется как${\displaystyle h_{\text{in}}(G)}$

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

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

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

Когда G является d - регулярным , возможно линейное алгебраическое определение расширения, основанное на собственных значениях матрицы смежности A = A ( G ) G , где количество ребер между вершинами i и j . ^[5] Поскольку A симметричен , из спектральной теоремы следует, что A имеет n действительных собственных значений . Известно, что все эти собственные значения лежат в [− d ,${\displaystyle A_{ij}}$${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$d ] и, более конкретно, известно, что λ _n = − d тогда и только тогда , когда G двудольна.

Более формально мы называем -вершинный, -регулярный граф как -граф . Граница, заданная -графом для for , полезна во многих контекстах, включая лемму о смешивании расширителей .${\displaystyle n}$${\displaystyle d}$${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$${\displaystyle (n,d,\lambda )}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda _{i}}$${\displaystyle i\neq 1}$

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

Если мы установим , так как это наибольшее собственное значение, соответствующее собственному вектору, ортогональному u , его можно эквивалентно определить с помощью отношения Рэлея :${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

${\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}}$

Нормализованные версии этих определений также широко используются и более удобны для формулировки некоторых результатов. Здесь рассматривается матрица , которая является марковской переходной матрицей графа G . Его собственные значения находятся в диапазоне от -1 до 1. Для не обязательно регулярных графов спектр графа можно определить аналогичным образом, используя собственные значения матрицы Лапласа . Для ориентированных графов рассматриваются сингулярные значения матрицы смежности A , которые равны корням собственных значений симметричной матрицы A ^T A .${\displaystyle {\tfrac {1}{d}}A}$

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

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

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

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

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

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

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

На самом деле это неравенство жесткое. Нижняя оценка достигается для гиперкуба , где и , а верхняя – для цикла, где и . ^[1] Это неравенство тесно связано с оценкой Чигера для цепей Маркова и может рассматриваться как дискретная версия неравенства Чигера в римановой геометрии .${\displaystyle Q_{n}}$${\displaystyle h(G)=1}$${\displaystyle d-\lambda =2}$${\displaystyle H(C_{n})=\Theta (1/n)}$${\displaystyle d-\lambda =\Theta (1/n^{2})}$

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

${\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})}}.}$

Асимптотически говоря, величины , и все ограничены сверху спектральной щелью .${\displaystyle {\frac {h^{2}}{d}}}$${\displaystyle h_{\text{out}}}$${\displaystyle h_{\text{in}}^{2}}$${\displaystyle O(d-\lambda _{2})}$

Конструкции

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

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

Алгебраические конструкции на основе графов Кэли известны для различных вариантов графов-расширителей. Следующая конструкция принадлежит Маргулису и была проанализирована Габбером и Галилом. ^[13] Для каждого натурального числа 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 -регулярные графы удовлетворяют , где - второе по величине собственное значение по модулю. ^[14] Как прямое следствие, мы знаем, что для каждого фиксированного и существует только конечное число -графов. Графы Рамануджана являются d -регулярными графами, для которых эта граница точна, удовлетворяя . ^[15] Следовательно, графы Рамануджана имеют асимптотически наименьшее возможное значение . Это делает их отличными расширителями спектра.${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$${\displaystyle \lambda _{2}}$${\displaystyle d}$${\displaystyle \lambda <2{\sqrt {d-1}}}$${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}}$${\displaystyle \lambda _{2}}$

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

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

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

В 2003 году Джоэл Фридман доказал гипотезу и уточнил, что имеется в виду под «наиболее регулярными графами», показав, что случайные d -регулярные графы имеют для каждого с вероятностью , где . ^{[18] [19]}${\displaystyle d}$${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$${\displaystyle \varepsilon >0}$${\displaystyle 1-O(n^{\tau })}$${\displaystyle \tau =\lceil ({\sqrt {d-1}}+1)/2\rceil }$

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

Рейнгольд , Вадхан и Вигдерсон представили зигзагообразное произведение в 2003 году. ^[20] Грубо говоря, зигзагообразное произведение двух графов-расширителей дает граф лишь с немного худшим расширением. Следовательно, зигзагообразное произведение также можно использовать для построения семейств графов-расширителей. Если является -графом и является -графом, то зигзагообразный продукт является -графом , обладающим следующими свойствами.${\displaystyle G}$${\displaystyle (n,m,\lambda _{1})}$${\displaystyle H}$${\displaystyle (m,d,\lambda _{2})}$${\displaystyle G\circ H}$${\displaystyle (nm,d^{2},\varphi (\lambda _{1},\lambda _{2},))}$${\displaystyle \varphi }$

1. Если и , то ;${\displaystyle \lambda _{1}<1}$${\displaystyle \lambda _{2}<1}$${\displaystyle \varphi (\lambda _{1},\lambda _{2})<1}$
2. ${\displaystyle \varphi (\lambda _{1},\lambda _{2})\leq \lambda _{1}+\lambda _{2}}$.

В частности, . ^[20]${\displaystyle f(\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) подразумевает, что зигзагообразное произведение двух графов-расширителей также является графом-расширителем, поэтому зигзагообразные произведения можно использовать индуктивно для создания семейства графов-расширителей.

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

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

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

Есть много результатов, которые показывают существование графов с хорошими свойствами расширения с помощью вероятностных аргументов. На самом деле существование экспандеров было впервые доказано Пинскером ^[21] , который показал, что для случайно выбранной вершины левый регулярный двудольный граф , для всех подмножеств вершин с высокой вероятностью, где – константа, зависящая от того, – . Алон и Ройхман ^[22] показали, что для каждой группы порядка и любого , существует такое, что граф Кэли на с образующими является расширителем, т.е. имеет второе собственное значение меньше, чем${\displaystyle n}$${\displaystyle d}$${\displaystyle |N(S)|\geq (d-2)|S|}$${\displaystyle |S|\leq c_{d}n}$${\displaystyle c_{d}}$${\displaystyle d}$${\displaystyle O(d^{-4})}$${\displaystyle G}$${\displaystyle n}$${\displaystyle 1>\varepsilon >0}$${\displaystyle c(\varepsilon )>0}$${\displaystyle G}$${\displaystyle c(\varepsilon )\log _{2}n}$${\displaystyle \varepsilon }$${\displaystyle 1-\varepsilon }$, с большой вероятностью.

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

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

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

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

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

Лемма о смешивании экспандеров утверждает, что для -графа для любых двух подмножеств вершин S , T ⊆ V , количество ребер между S и T примерно равно тому, что вы ожидаете в случайном d -регулярном графе. Аппроксимация тем лучше, чем меньше . В случайном d - регулярном графе, а также в случайном графе Эрдёша–Реньи с вероятностью ребра d / n мы ожидаем ребра между S и T.${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda }$${\displaystyle {\tfrac {d}{n}}\cdot |S|\cdot |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|}}.}$

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

• Независимое множество графа — это подмножество вершин, в котором нет двух смежных вершин. В -графе независимое множество имеет размер не более .${\displaystyle (n,d,\lambda )}$${\displaystyle \lambda n/d}$
• Хроматическое число графа , , - это минимальное количество цветов, необходимых для того, чтобы смежные вершины имели разные цвета. Хоффман показал, что , ^[23] а Алон, Кривелевич и Судаков показали, что если , то . ^[24]${\displaystyle G}$${\displaystyle \chi (G)}$${\displaystyle d/\lambda \leq \chi (G)}$${\displaystyle d<2n/3}$${\displaystyle \chi (G)\leq O(d/\log(1+d/\lambda ))}$
• Диаметр графа — это максимальное расстояние между двумя вершинами , где расстояние между двумя вершинами определяется как кратчайший путь между ними. Чанг показал, что диаметр -графа не превышает . ^[25]${\displaystyle (n,d,\lambda )}$${\displaystyle \lceil \log n/\log(d/\lambda )\rceil }$

Семплирование экспандера

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

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

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

В сети сортировки AKS графы-расширители используются для построения ограниченных половин глубины . -halver принимает в качестве входных данных перестановку длины и делит входные данные пополам на два непересекающихся множества и так, что для каждого целого числа не более наименьших входных данных находятся в , а большинство самых больших входных данных находятся в . Множества и делятся пополам.${\displaystyle \varepsilon }$${\displaystyle \varepsilon }$${\displaystyle n}$${\displaystyle (1,\ldots ,n)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle k\leq n/2}$${\displaystyle \varepsilon k}$${\displaystyle k}$${\displaystyle B}$${\displaystyle \varepsilon k}$${\displaystyle k}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle \varepsilon }$

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

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

После всех раундов примите за набор входных данных в регистрах in и за набор входных данных в регистрах in , чтобы получить -уполовинивание. Чтобы убедиться в этом, заметьте, что если регистры in и in соединены ребром, то после обработки сопоставления с этим ребром вход in будет меньше, чем у . Кроме того, это свойство остается верным на протяжении всего остального процесса. Теперь предположим, что для некоторых из них в . Тогда по свойствам расширения графа регистры этих входов связаны как минимум с регистрами в${\displaystyle d}$${\displaystyle A}$${\displaystyle X}$${\displaystyle B}$${\displaystyle Y}$${\displaystyle \varepsilon }$${\displaystyle u}$${\displaystyle X}$${\displaystyle v}$${\displaystyle Y}$${\displaystyle uv}$${\displaystyle u}$${\displaystyle v}$${\displaystyle k\leq n/2}$${\displaystyle \varepsilon k}$${\displaystyle (1,\ldots ,k)}$${\displaystyle B}$${\displaystyle Y}$${\displaystyle {\frac {1-\varepsilon }{\varepsilon }}k}$${\displaystyle X}$. В целом, это больше, чем просто регистры, поэтому должен быть какой-то регистр , соединенный с каким-то регистром , таким образом, чтобы окончательный ввод не был в , а окончательный ввод был. Однако это нарушает предыдущее свойство, и, таким образом, выходные наборы должны быть -половинками.${\displaystyle k}$${\displaystyle a}$${\displaystyle X}$${\displaystyle b}$${\displaystyle Y}$${\displaystyle a}$${\displaystyle (1,\ldots ,k)}$${\displaystyle b}$${\displaystyle A}$${\displaystyle B}$${\displaystyle \varepsilon }$

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

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

Примечания

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

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

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