График расширителя

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

Определения [ править ]

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

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

Расширение края [ править ]

Расширение ребер (также изопериметрическое число или константа Чигера ) 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 \}.}$

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

Расширение вершин [ править ]

Вершина изопериметрическое число (также расширение вершин или увеличение ) графа 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 является д -регулярного , А линейное алгебраическое определение разложения возможно на основе собственных значений в матрице смежности = A ( G ) из G , где есть число ребер между вершинами я и J . ^[5] Из - за является симметричным , то спектральной теорема означает , что имеет п вещественных собственные значений . Известно, что все эти собственные значения лежат в [- d ,${\displaystyle A_{ij}}$${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$г ].

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

Известно, что λ _n = - d тогда и только тогда, когда G двудольна. Во многих контекстах, например в лемме о смешивании расширителей , ограничения на λ ₂ недостаточно, но на самом деле необходимо ограничить абсолютное значение всех собственных значений вдали от d :

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

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

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

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

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

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

Неравенства Чигера [ править ]

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

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{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 \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}}$${\displaystyle \lambda _{2}}$

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

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

для каждого с вероятностью, поскольку n стремится к бесконечности. ^[17]${\displaystyle \varepsilon >0}$${\displaystyle 1-o(1)}$

Приложения и полезные свойства [ править ]

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

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

Лемма о смешивании расширителей [ править ]

Лемма о расширительном смешивании утверждает, что для любых двух подмножеств вершин S , T ⊆ V количество ребер между S и T приблизительно соответствует тому, что вы ожидаете от случайного d -регулярного графа. Приближение тем лучше, чем меньше . В случайном г -регулярного график, а также в случайном графе Эрдеш-Рении с вероятностью края г / л , мы ожидаем , что ребра между S и T .${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$${\displaystyle {\tfrac {d}{n}}\cdot |S|\cdot |T|}$

Более формально, пусть Е ( 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, 1], с высокой вероятностью среднее из наших образцов близко к ожиданию случайной величины. В лемме о выборке обхода расширителя, предложенной Ajtai, Komlós & Szemerédi (1987) и Gillman (1998) , утверждается, что это также верно при отборе образцов от обхода на расширяющем графе. Это особенно полезно в теории дерандомизации , поскольку выборка в соответствии с обходом расширителя использует намного меньше случайных битов, чем независимая выборка.

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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