Лемма о перемешивании расширителей - Expander mixing lemma - Wikipedia

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

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

Определить ${\displaystyle (n,d,\lambda )}$-граф быть ${\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 (n,d,\lambda )}$-графы образуют семейство графики расширителей с постоянным спектральный промежуток.

Заявление

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

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

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

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

${\displaystyle \left|e(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\subseteq L,T\subseteq R}$ с ${\displaystyle |S|=\alpha |L|}$ и ${\displaystyle |T|=\beta |R|}$. Позволять ${\displaystyle e(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 n\times n}$ матрица всех единиц. Обратите внимание, что ${\displaystyle v_{1}}$ является собственным вектором ${\displaystyle J}$ с собственным значением ${\displaystyle n}$ и друг друга ${\displaystyle v_{i}}$, будучи перпендикулярным ${\displaystyle v_{1}=\mathbf {1} }$, является собственным вектором ${\displaystyle J}$ с собственным значением 0. Для подмножества вершин ${\displaystyle U\subseteq V}$, позволять ${\displaystyle 1_{U}}$ быть вектор-столбцом с ${\displaystyle v^{\text{th}}}$ координата равна 1, если ${\displaystyle v\in U}$ и 0 в противном случае. Потом,

${\displaystyle \left|e(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|e(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)^{\operatorname {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|e(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 (n,d,\lambda )}$-граф не более ${\displaystyle \lambda n/d.}$ Это доказывается положением ${\displaystyle T=S}$ в заявлении выше и используя тот факт, что ${\displaystyle e(S,S)=0.}$

Дополнительным следствием является то, что если ${\displaystyle G}$ является ${\displaystyle (n,d,\lambda )}$-граф, то его хроматическое число ${\displaystyle \chi (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\subseteq V}$ с ${\displaystyle S\cap T=\emptyset }$ у нас есть

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

то его второе по величине (по модулю) собственное значение ограничено ${\displaystyle O(\lambda (1+\log(d/\lambda )))}$.

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

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

Позволять ${\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}|}}.}$

Примечания

1. Вадхан, Салил (весна 2009 г.). «Расширительные графики» (PDF). Гарвардский университет. Получено 1 декабря, 2019.
2. См. Теорему 5.1 в книге Хемерса «Чередование собственных значений и графиков».
3. Лемма о перемешивании расширителей, обратная

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

• 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.