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

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

d - Обычные расширенные графики

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

Если мы исправим $d$ и $\lambda$ затем $(n,d,\lambda )$-графы образуют семейство графов-расширителей с постоянной спектральной щелью .

Заявление

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

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

более тесная связь

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

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

используя аналогичные техники.

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

Для бирегулярных графов имеем следующий вариант, где мы берем $\lambda$ быть вторым по величине собственным значением.

Позволять $G=(L,R,E)$ — двудольный граф такой, что каждая вершина в $L$ находится рядом с $d_{L}$ вершины $R$ и каждая вершина в $R$ находится рядом с $d_{R}$ вершины $L$. Позволять $S\subseteq L,T\subseteq R$ с $|S|=\alpha |L|$ и $|T|=\beta |R|$. Позволять $e(G)=|E(G)|$. Затем

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

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

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

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

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

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

$\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|$.

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

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

Это означает, что $\|M1_{T}\|\leq \lambda \|1_{T}\|$ и $\left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \lambda \|1_{S}\|\|1_{T}\|=\lambda {\sqrt {|S||T|}}$.

Доказательство более жесткой границы

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

$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)$

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

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

Мы можем связать правую часть с помощью $\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)}}$ используя те же методы, что и в предыдущем доказательстве.

Приложения

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

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

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

Конверсы

Билу и Линиал показали справедливо и обратное: если $d$-регулярный график $G=(V,E)$ удовлетворяет тому, что для любых двух подмножеств $S,T\subseteq V$ с $S\cap T=\emptyset$ у нас есть

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

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

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

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

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

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

Ссылки

• Алон, Н.; Чунг, ФРК (1988), «Явное построение толерантных сетей линейного размера», Discrete Mathematics , 72 (1–3): 15–19, CiteSeerX   10.1.1.300.7495 , doi : 10.1016/0012-365X(88)90189- 6 .
• ФК Буссемейкер, ДМ Цветкович, Джей Джей Зайдель. Графы, связанные с исключительными корневыми системами, Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), том 18 коллоквиума. Математика. Сок. Янош Бояи (1978), 185–191.

• Хемерс, WH (1979). Методы собственных значений в дизайне и теории графов (PDF) (доктор философии).
• Хемерс, WH (1995), «Переплетение собственных значений и графиков» , Приложение к линейной алгебре. , 226 : 593–616, doi : 10.1016/0024-3795(95)00199-2 .

• Хори, С.; Линиал, Н.; Вигдерсон, А. (2006), «Расширяющие графы и их приложения» (PDF) , Bull. амер. Математика. Соц. (NS) , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8 .

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