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

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

Определения

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

Вершинное расширение

Вершина изопериметрическое число (также расширение вершин или увеличение ) графа 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 . В одном из вариантов этого определения (называется уникальное расширение соседа ) заменяется множеством вершин в V с ровно один сосед в S . ${\ 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 , по меньшей мере , с одним соседом . ${\ displaystyle \ partial _ {\ text {in}} (S)}$${\ Displaystyle V (G) \ setminus S}$

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

Когда G является д -регулярного , А линейное алгебраическое определение разложения возможно на основе собственных значений в матрице смежности = A ( G ) из G , где есть число ребер между вершинами я и J . Поскольку является симметричным , то спектральной теорема означает , что имеет п вещественных собственные значений . Известно, что все эти собственные значения лежат в [- d , 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 и \ в \ mathbb {R} ^ {п}}$${\ displaystyle u_ {i} = 1 / n}$

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

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

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

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

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

Конструкции

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

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

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

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

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

для каждого с вероятностью, поскольку n стремится к бесконечности. ${\ 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) , утверждается, что это также верно при выборке из обхода на расширяющем графе. Это особенно полезно в теории дерандомизации , поскольку выборка в соответствии с обходом расширителя использует намного меньше случайных битов, чем независимая выборка.

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

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

Заметки

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

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

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