Лемма о перемешивании расширителей - Википедия - Expander mixing lemma

В расширитель лемма о перемешивании интуитивно заявляет, что края определенных ${ displaystyle d}$-регулярные графы равномерно распределены по всему графу. В частности, количество ребер между двумя подмножествами вершин ${ displaystyle S}$ и ${ displaystyle T}$ всегда близко к ожидаемому количеству ребер между ними в случайный ${ displaystyle d}$-регулярный график, а именно ${ displaystyle { frac {d} {n}} | S || T |}$.

${ displaystyle d}$-Регулярные графики расширителя

Определить ${ Displaystyle (п, д, лямбда)}$-граф быть ${ displaystyle d}$-регулярный график ${ displaystyle G}$ на ${ displaystyle n}$ вершины такие, что все собственные значения его матрицы смежности ${ displaystyle A_ {G}}$ кроме одного иметь величину не больше ${ displaystyle lambda.}$ В ${ displaystyle d}$-регулярность графика гарантирует, что его собственное значение наибольшей величины будет ${ displaystyle d.}$ Фактически, вектор всех единиц ${ displaystyle mathbf {1}}$ является собственным вектором ${ displaystyle A_ {G}}$ с собственным значением ${ displaystyle d}$, а собственные векторы матрицы смежности никогда не будет превышать максимальную степень ${ displaystyle G}$ по величине.

Если мы исправим ${ displaystyle d}$ и ${ displaystyle lambda}$ тогда ${ Displaystyle (п, д, лямбда)}$-графы образуют семейство графики расширителей с постоянным спектральный промежуток.

Заявление

Позволять ${ Displaystyle G = (V, E)}$ быть ${ Displaystyle (п, д, лямбда)}$-граф. Для любых двух подмножеств ${ displaystyle S, T substeq V}$, позволять ${ Displaystyle е (S, T) = | {(x, y) in S times T: xy in E (G) } |}$ быть количеством ребер между S и Т (считая ребра, содержащиеся в пересечении S и Т дважды). потом

${ displaystyle left | е (S, T) - { frac {d | S || T |} {n}} right | leq lambda { sqrt {| S || T |}} , .}$

Более плотная связь

Фактически мы можем показать, что

${ displaystyle left | е (S, T) - { frac {d | S || T |} {n}} right | leq lambda { sqrt {| S || T | (1- | S | / n) (1- | T | / n)}} ,}$

используя аналогичные методы.^[1]

Бирегулярные графы

За бирегулярные графы, имеем следующий вариант.^[2]

Позволять ${ Displaystyle G = (L, R, E)}$ - двудольный граф такой, что каждая вершина в ${ displaystyle L}$ примыкает к ${ displaystyle d_ {L}}$ вершины ${ displaystyle R}$ и каждая вершина в ${ displaystyle R}$ примыкает к ${ displaystyle d_ {R}}$ вершины ${ displaystyle L}$. Позволять ${ Displaystyle S substeq L, T substeq R}$ с ${ Displaystyle | S | = альфа | L |}$ и ${ displaystyle | T | = beta | R |}$. Позволять ${ Displaystyle е (G) = | E (G) |}$. потом

${ displaystyle left | { frac {e (S, T)} {e (G)}} - alpha beta right | leq { frac { lambda} { sqrt {d_ {L} d_ {R}}}} { sqrt { alpha beta (1- alpha) (1- beta)}} leq { frac { lambda} { sqrt {d_ {L} d_ {R}} }} { sqrt { alpha beta}} ,.}$

Обратите внимание, что ${ displaystyle { sqrt {d_ {L} d_ {R}}}}$ - наибольшая абсолютная величина собственных значений ${ displaystyle G}$.

Доказательства

Доказательство первого утверждения

Позволять ${ displaystyle A_ {G}}$ быть матрица смежности из ${ displaystyle G}$ и разреши ${ displaystyle lambda _ {1} geq cdots geq lambda _ {n}}$ быть собственными значениями ${ displaystyle A_ {G}}$ (эти собственные значения действительны, потому что ${ displaystyle A_ {G}}$ симметрично). Мы знаем это ${ displaystyle lambda _ {1} = d}$ с соответствующим собственным вектором ${ displaystyle v_ {1} = { frac {1} { sqrt {n}}} mathbf {1}}$, нормализация вектора всех единиц. Потому что ${ displaystyle A_ {G}}$ симметричен, мы можем выбрать собственные векторы ${ displaystyle v_ {2}, ldots, v_ {n}}$ из ${ displaystyle A_ {G}}$ соответствующие собственным значениям ${ displaystyle lambda _ {2}, ldots, lambda _ {n}}$ так что ${ Displaystyle {v_ {1}, ldots, v_ {n} }}$ образует ортонормированную основу ${ displaystyle mathbf {R} ^ {n}}$.

Позволять ${ displaystyle J}$ быть ${ Displaystyle п раз п}$ матрица всех единиц. Обратите внимание, что ${ displaystyle v_ {1}}$ является собственным вектором ${ displaystyle J}$ с собственным значением ${ displaystyle n}$ и друг друга ${ displaystyle v_ {i}}$, будучи перпендикулярным ${ displaystyle v_ {1} = mathbf {1}}$, является собственным вектором ${ displaystyle J}$ с собственным значением 0. Для подмножества вершин ${ Displaystyle U substeq V}$, позволять ${ displaystyle 1_ {U}}$ быть вектор-столбцом с ${ displaystyle v ^ { text {th}}}$ координата равна 1, если ${ displaystyle v in U}$ и 0 в противном случае. Потом,

${ displaystyle left | е (S, T) - { frac {d} {n}} | S || T | right | = left | 1_ {S} ^ { operatorname {T}} left (A_ {G} - { frac {d} {n}} J right) 1_ {T} right |}$.

Позволять ${ displaystyle M = A_ {G} - { frac {d} {n}} J}$. Потому что ${ displaystyle A_ {G}}$ и ${ displaystyle J}$ разделяют собственные векторы, собственные значения ${ displaystyle M}$ находятся ${ displaystyle 0, lambda _ {2}, ldots, lambda _ {n}}$. Посредством Неравенство Коши-Шварца у нас есть это ${ displaystyle | 1_ {S} ^ { operatorname {T}} M1_ {T} | = | 1_ {S} cdot M1_ {T} | leq | 1_ {S} | | M1_ {T} |}$. Кроме того, поскольку ${ displaystyle M}$ самосопряженный, мы можем написать

${ Displaystyle | M1_ {T} | ^ {2} = langle M1_ {T}, M1_ {T} rangle = langle 1_ {T}, M ^ {2} 1_ {T} rangle = left langle 1_ {T}, sum _ {i = 1} ^ {n} M ^ {2} langle 1_ {T}, v_ {i} rangle v_ {i} right rangle = sum _ {i = 2} ^ {n} lambda _ {i} ^ {2} langle 1_ {T}, v_ {i} rangle ^ {2} leq lambda ^ {2} | 1_ {T} | ^ {2}}$.

Отсюда следует, что ${ Displaystyle | M1_ {T} | leq lambda | 1_ {T} |}$ и ${ displaystyle left | е (S, T) - { frac {d} {n}} | S || T | right | leq lambda | 1_ {S} | | 1_ {T} | = lambda { sqrt {| S || T |}}}$.

Доказательство более тесной связи

Чтобы показать более точную оценку выше, мы вместо этого рассматриваем векторы ${ displaystyle 1_ {S} - { frac {| S |} {n}} mathbf {1}}$ и ${ displaystyle 1_ {T} - { frac {| T |} {n}} mathbf {1}}$, которые оба перпендикулярны ${ displaystyle v_ {1}}$. Мы можем расширить

${ displaystyle 1_ {S} ^ { operatorname {T}} A_ {G} 1_ {T} = left ({ frac {| S |} {n}} mathbf {1} right) ^ { имя оператора {T}} A_ {G} left ({ frac {| T |} {n}} mathbf {1} right) + left (1_ {S} - { frac {| S |} { n}} mathbf {1} right) ^ { operatorname {T}} A_ {G} left (1_ {T} - { frac {| T |} {n}} mathbf {1} right )}$

потому что два других члена разложения равны нулю. Первый член равен ${ displaystyle { frac {| S || T |} {n ^ {2}}} mathbf {1} ^ { operatorname {T}} A_ {G} mathbf {1} = { frac {d } {n}} | S || T |}$, поэтому мы находим, что

${ displaystyle left | е (S, T) - { frac {d} {n}} | S || T | right | leq left | left (1_ {S} - { frac {| S |} {n}} mathbf {1} right) ^ { operatorname {T}} A_ {G} left (1_ {T} - { frac {| T |} {n}} mathbf { 1} right) right |}$

Мы можем связать правую часть с помощью ${ displaystyle lambda left | 1_ {S} - { frac {| S |} {| n |}} mathbf {1} right | left | 1_ {T} - { frac { | T |} {| n |}} mathbf {1} right | = lambda { sqrt {| S || T | left (1 - { frac {| S |} {n}} right) left (1 - { frac {| T |} {n}} right)}}}$ используя те же методы, что и в предыдущем доказательстве.

Приложения

Лемму о смешивании расширителей можно использовать для оценки сверху размера независимого набора в графе. В частности, размер независимого множества в ${ Displaystyle (п, д, лямбда)}$-граф не более ${ displaystyle lambda n / d.}$ Это доказывается положением ${ displaystyle T = S}$ в заявлении выше и используя тот факт, что ${ Displaystyle е (S, S) = 0.}$

Дополнительным следствием является то, что если ${ displaystyle G}$ является ${ Displaystyle (п, д, лямбда)}$-граф, то его хроматическое число ${ Displaystyle чи (G)}$ по крайней мере ${ displaystyle d / lambda.}$ Это потому, что в допустимой раскраске графа набор вершин данного цвета является независимым набором. По вышеуказанному факту, каждый независимый набор имеет размер не более ${ displaystyle lambda n / d,}$ так по крайней мере ${ displaystyle d / lambda}$ такие наборы нужны, чтобы покрыть все вершины.

Второе применение леммы о смешивании расширителей - обеспечить верхнюю границу максимально возможного размера независимого набора в графе полярности. Учитывая конечное проективная плоскость ${ displaystyle pi}$ с полярность ${ displaystyle perp,}$ граф полярности - это граф, вершинами которого являются точки a ${ displaystyle pi}$, а вершины ${ displaystyle x}$ и ${ displaystyle y}$ связаны тогда и только тогда, когда ${ displaystyle x in y ^ { perp}.}$ В частности, если ${ displaystyle pi}$ есть заказ ${ displaystyle q,}$ то лемма о смешивании расширителей может показать, что независимое множество в графе полярностей может иметь размер не более ${ displaystyle q ^ {3/2} -q + ​​2q ^ {1/2} -1,}$ оценка, доказанная Хобартом и Уиллифордом.

Converse

Билу и Linial показал^[3] верно и обратное: если ${ displaystyle d}$-регулярный график ${ Displaystyle G = (V, E)}$ удовлетворяет тому, что для любых двух подмножеств ${ displaystyle S, T substeq V}$ с ${ Displaystyle S cap T = emptyset}$ у нас есть

${ displaystyle left | е (S, T) - { frac {d | S || T |} {n}} right | leq lambda { sqrt {| S || T |}},}$

то его второе по величине (по модулю) собственное значение ограничено ${ Displaystyle О ( лямбда (1+ журнал (д / лямбда)))}$.

Обобщение на гиперграфы

Фридман и Виджерсон доказали следующее обобщение леммы о перемешивании на гиперграфы.

Позволять ${ displaystyle H}$ быть ${ displaystyle k}$-равномерный гиперграф, т.е. гиперграф, в котором каждое «ребро» является набором ${ displaystyle k}$ вершины. Для любого выбора подмножеств ${ displaystyle V_ {1}, ..., V_ {k}}$ вершин,

${ displaystyle left || e (V_ {1}, ..., V_ {k}) | - { frac {k! | E (H) |} {n ^ {k}}} | V_ {1 } | ... | V_ {k} | right | leq lambda _ {2} (H) { sqrt {| V_ {1} | ... | V_ {k} |}}.}$

Примечания

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

• Alon, N .; Чанг, Ф. Р. К. (1988), "Явное построение терпимых сетей линейного размера", Дискретная математика, 72 (1–3): 15–19, Дои:10.1016 / 0012-365X (88) 90189-6.

• Хемерс, В. Х. (1979). Методы собственных значений в теории дизайна и графов (PDF) (Кандидат наук.).
• Хемерс, В. Х. (1995), «Чередование собственных значений и графиков», Линейная алгебра Appl., 226: 593–616, Дои:10.1016/0024-3795(95)00199-2.

• Hoory, S .; Linial, N .; Вигдерсон, А. (2006), «Графы-расширители и их приложения» (PDF), Бык. Амер. Математика. Soc. (Н.С.), 43 (4): 439–561, Дои:10.1090 / S0273-0979-06-01126-8.

• Friedman, J .; Виджерсон, А. (1995), «О втором собственном значении гиперграфов» (PDF), Комбинаторика, 15 (1): 43–65, Дои:10.1007 / BF01294459, S2CID  17896683.