익스팬더 혼합 보조정리

익스팬더 혼합 보조정리기는 특정 $d{\displaystyle }$ ${\displaystyle d}-$정규$$ 그래프의 가장자리가 그래프 전체에 고르게 분포되어 있다고 직관적으로 설명한다.특히 두 꼭지점 부분 $집합{\displaystyle }$ S ${\displaystyle S}$과 T ${\displaystyle T}$ 사이의 에지 수는 랜덤 $d{\displaystyle }$ ${\displaystyle d}$ -정규$$ 그래프, $즉{\displaystyle \frac{}{}}$ ${\displaystyle dn}$ ${\displaystyle S}$ ${\d}{n}S T$}에서 항상 예상되는 에지 수에 가깝다$.$

d-일반 확장기 그래프

Define an ${\displaystyle (n,d,\lambda )}$-graph to be a ${\displaystyle d}$-regular graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices such that all of the eigenvalues of its adjacency matrix ${\displaystyle A_{G}}$ except one have absolute value at most ${\displaystyle \lam$$bda .}$ The ${\displaystyle d}$-regularity of the graph guarantees that its largest absolute value of an eigenvalue is ${\displaystyle d.}$ In fact, the all-1's vector ${\displaystyle \mathbf {1} }$ is an eigenvector of ${\displaystyle A_{G}}$ with eigenvalue ${\displaystyle d}$, and the eigenvalue인접 행렬의 s는 절대값의$$ $최대{\displaystyle }$ G ${\displaystyle G}$을(를) 초과하지 않는다.

$d{\displaystyle }$ ${\displaystyle d}$ 및$$$and{\displaystyle }$ {\$displaystyle \lambda }$을(를) 수정하면$$ (${\displaystyle n}$ ,${\displaystyle }$d ,${\displaystyle \lambda }$)${\ddaystyle (n,d,\lambda )}$ -그래프는$$ 일정한 스펙트럼 갭을 갖는 확장형 그래프 계열을 형성한다.

성명서

$G{\displaystyle }$=${\displaystyle }$( ${\displaystyle V}$, ${\displaystyle E}$) ${\displaystyle$ G$=(V,E)}$을(를) $({\displaystyle n}$, d ,${\displaystyle \lambda }$) ${\displaystyle (n,d,\lambda )}$ -그래프로$$ 한다$$.For any two subsets ${\displaystyle S,T\subseteq V}$, let ${\displaystyle e(S,T)= \{(x,y)\in S\times T:xy\in E(G)\} }$ be the number of edges between S and T (counting edges contained in the intersection of S and T twice).그러면

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

더 촘촘한 경계

사실 우리는 그것을 보여줄 수 있다.

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

유사한 ^[1]기술을 사용하여

2차 그래프

2차 그래프의 경우 다음과 같은 변동이 있다.^[2]

Let ${\displaystyle G=(L,R,E)}$ be a bipartite graph such that every vertex in ${\displaystyle L}$ is adjacent to ${\displaystyle d_{L}}$ vertices of ${\displaystyle R}$ and every vertex in ${\displaystyle R}$ is adjacent to ${\displaystyle d_{R}}$ vertices of ${\dis$$playstyle L}$. Let ${\displaystyle S\subseteq L,T\subseteq R}$ with ${\displaystyle S =\alpha L }$ and ${\displaystyle T =\beta R }$. Let ${\displaystyle e(G)= E(G) }$. Then

${\displaystyle \왼쪽 {\frac {e,T)}{e(G)}-\alpha \beta \right \leq {\frac {\lambda }{\sqrt {d_{\sqrt}{\sqrt}}{}L}d_{R}}}{\sqrt {\\sqrt {\alpha \beta )(1-\beta )}}}\leq {\frac {\lambda}{\sqrt {d_{\sqrt {d_{}}}}}{{\sqrt}}{{{}}}}}}}}}}L}d_{R}}}{\\sqrt {\\alpha \beta }}}\,}$

$d{\displaystyle \sqrt{{}_{}}}$ ${\displaystyle \sqrt{L_{}}}$ ${\displaystyle \sqrt{{}_{}{}_{}}}$ ${\displaystyle \sqrt{R_{}}}$ ${\$$L}d_{R}}}}$은(는) $G{\displaystyle }$ ${\displaystyle G}$의 고유값 중 가장 큰 절대값이다$.$

교정쇄

첫 번째 진술의 증명

Let ${\displaystyle A_{G}}$ be the adjacency matrix of ${\displaystyle G}$ and let ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{n}}$ be the eigenvalues of ${\displaystyle A_{G}}$ (these eigenvalues are real because ${\displaystyle A_{G}}$ is symmetric).$\lambda {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle d}$ ${\displaystyle \lambda_{1}=d}$에 해당하는 고유 벡터 ${\displaystyle {v\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$= ${\displaystyle \frac{\sqrt{1n}}{}}$ ${\displaystyle \frac{}{}\mathbf{}}$ ${\$ {$1},$all-1의 벡터 정규화$.$Define ${\displaystyle \lambda ={\sqrt {\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}}}}$ and note that ${\displaystyle \max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}\leq \lambda ^{2}\leq \lambda _{1}^{2}=d^{2}}$.Because ${\displaystyle A_{G}}$ is symmetric, we can pick eigenvectors ${\displaystyle v_{2},\ldots ,v_{n}}$ of ${\displaystyle A_{G}}$ corresponding to eigenvalues ${\displaystyle \lambda _{2},\ldots ,\lambda _{n}}$ so that ${\display$$스타일 \{v_{1},\ldots,v_{n}\}}}$은(는) $R{\displaystyle {\mathbf{}}^{}}$ ${\displaystyle {}^{}}$ ${\$의 정형 기준을 형성한다$.$

$J{\displaystyle }$ ${\displaystyle J}$을(를) 모든 1의 $매트릭스$ n${\displaystyle }$× ${\displaystyle n}${\$displaystyle n\times$ n$}$ 행렬로$$ 두십시오.Note that ${\displaystyle v_{1}}$ is an eigenvector of ${\displaystyle J}$ with eigenvalue ${\displaystyle n}$ and each other ${\displaystyle v_{i}}$, being perpendicular to ${\displaystyle v_{1}=\mathbf {1} }$, is an eigenvector of ${\displaystyle J}$ with eigenvalue 0.꼭지점 부분 $집합{\displaystyle }$ U${\displaystyle v}$ V$${\$displaystyle U\subseteq V}$의 경우 $1{\displaystyle {}^{}}$ $U{\displaystyle {\mathrm{}}_{}}$ ${\$ $v$$^{\text{{U}}}$을(를) v ${\displaystyle \in }$ ${\displaystyle U}$ ${\displaystystyle v^{\in U}$와 다른 경우 1과 ${\displaystyle {같은}_{}}$ 좌표가$$ 되도록$$ 한다$.$그러면

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

Let ${\displaystyle M=A_{G}-{\frac {d}{n}}J}$. Because ${\displaystyle A_{G}}$ and ${\displaystyle J}$ share eigenvectors, the eigenvalues of ${\displaystyle M}$ are ${\displaystyle 0,\lambda _{2},\ldots ,\lambda _{n}}$. By the Cauchy-Schwarz inequality, wehave that ${\displaystyle 1_{S}^{\operatorname {T} }M1_{T} = 1_{S}\cdot M1_{T} \leq \ 1_{S}\ \ M1_{T}\ }$. Furthermore, because ${\displaystyle M}$ is self-adjoint, we can write

${\displaystyle \ M1_{T}\ ^{2}=\langle M1_{T},M1_{T}\rangle =\langle 1_{T},M^{2}1_{T}\rangle =\left\langl$$e 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}}$.

This implies that ${\displaystyle \ M1_{T}\ \leq \lambda \ 1_{T}\ }$ and ${\displaystyle \left e(S,T)-{\frac {d}{n}} S T \right \leq \lambda \ 1_{S}\ \ 1_{T}\ =\lambda {\sqrt { S T }}}$.

더 촘촘한 경계 교정 스케치

To show the tighter bound above, we instead consider the vectors ${\displaystyle 1_{S}-{\frac { S }{n}}\mathbf {1} }$ and ${\displaystyle 1_{T}-{\frac { T }{n}}\mathbf {1} }$, which are both perpendicular to ${\displaystyle v_{1}}$. We can expand

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

팽창의 나머지 두 조건은 0이기 때문이다.The first term is equal to ${\displaystyle {\frac { S T }{n^{2}}}\mathbf {1} ^{\operatorname {T} }A_{G}\mathbf {1} ={\frac {d}{n}} S T }$, so we find that

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

We can bound the right hand side by ${\displaystyle \lambda \left\ 1_{S}-{\frac { S }{ n }}\mathbf {1} \right\ \left\ 1_{T}-{\frac { T }{ n }}\mathbf {1} \$$right\ =\lambda {\sqrt {S \{n}\right)\left$(1-${{{n}}\l$)\left$$$(1-{\frac{{{n}\right)}}}}}.$

적용들

익스팬더 혼합 보조정리기는 그래프에서 독립된 세트의 크기를 상회하는 데 사용될 수 있다.특히$,{\displaystyle }$ (${\displaystyle n}$, ${\displaystyle d}$ ,${\displaystyle \lambda }$) ${\displaystyle (n,d,\lambda )}$ -그래프는$$ 최대 ${\displaystyle \mathrm{\lambda n}}$ /${\displaystyle }$d${\displaystyle }$. ${\displaystyle \lambda$ n$/$$d$.$}$ 이는$$ $위$의 문장에$$ T${\displaystyle }$= ${\displaystyle S}$ ${\displaystyle T=S}$을(를) 넣고 $e{\displaystyle (S}$, ${\displaystyle S}$)${\displaystyle }$= ${\displaystyle 0.}$ ${\displaystyle e(S,S)=0.}$을(를) 사용함으로써 증명된다.

An additional consequence is that, if ${\displaystyle G}$ is an ${\displaystyle (n,d,\lambda )}$-graph, then its chromatic number ${\displaystyle \chi (G)}$ is at least ${\displaystyle d/\lambda .}$ This is because, in a valid graph coloring, the set of vertices of a given color is an independent 집합위의 사실에 의해, 각각의 독립형 집합은 최대 크기 ${\displaystyle \mathrm{nn}}$ ${\displaystyle /d}$ ,$${\$displaystyle \lambda n/d,}$을(를) 가지기 때문에$$, $적어도{\displaystyle d}$ / {$${\$displaystyle d/\lambda$} 이러한$$ 집합은 모든 정점을 커버하기 위해 필요하다.

익스팬더 혼합 보조정리기의 두 번째 적용은 극성 그래프 내에서 독립형 세트의 가능한 최대 크기에 상한을 제공하는 것이다.${\displaystyle {}^{}}$ $\perp {\displaystyle }$, ${\displaystyle \$$pi$}을$$(를) 가진 유한 투영 $평면{\displaystyle }$ {$${\$displaystyle$$$\$pi$}을(를) 볼 때 극성$$ 그래프는 $정점$이 {$${\$displaystystyle$ \$pi$$$$}$의 점이고,$$$정점{\displaystyle }$ x$$${\displaystyle \in }$ ${\displaystyle {\in }^{}}$ .${\st$.$yle x\in y^{\perp }.}$ In particular, if ${\displaystyle \pi }$ has order ${\displaystyle q,}$ then the expander mixing lemma can show that an independent set in the polarity graph can have size at most ${\displaystyle q^{3/2}-q+2q^{1/2}-1,}$ a bound proved by Hobart and Williford.

컨버스

Bilu and Linial showed^[3] that a converse holds as well: if a ${\displaystyle d}$-regular graph ${\displaystyle G=(V,E)}$ satisfies that for any two subsets ${\displaystyle S,T\subseteq V}$ with ${\displaystyle S\cap T=\emptyset }$ we have

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

두 번째로 큰(절대값에서) 고유값은 $O{\displaystyle }$(${\displaystyle 1}$+ ${\displaystyle \mathrm{로그}}$log ${\displaystyle (}$d${\displaystyle }$/ ${\displaystyle \lambda }$ ${\displaystyle ))}$로 제한된다${\displaystyle .}$ ${\displaystyle O(\lambda (1+\logda (d/\lambda$ $))\}).$

하이퍼그래프로 일반화

프리드먼과 위드거슨은 하이퍼그래프에 혼합 보조정리법을 다음과 같이 일반화한다는 것을 증명했다.

$H{\displaystyle }$ ${\displaystyle H}$을(를) $k{\displaystyle }$ ${\displaystyle k}$ -uniform$$ hypergraph, 즉 모든 "에지"가 $k{\displaystyle }$ ${\displaysty k}$ 꼭지점의$$ 튜플인 하이퍼그래프가 되도록$$ 한다.서브셋 $V{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$. . . . ${\displaystyle V_{}}$ 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.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics, 72 (1–3): 15–19, doi:10.1016/0012-365X(88)90189-6.

• Haemers, W. H. (1979). Eigenvalue Techniques in Design and Graph Theory (PDF) (Ph.D.).
• Haemers, W. H. (1995), "Interlacing Eigenvalues and Graphs", Linear Algebra Appl., 226: 593–616, doi:10.1016/0024-3795(95)00199-2.

• Hoory, S.; Linial, N.; Wigderson, A. (2006), "Expander Graphs and their Applications" (PDF), Bull. Amer. Math. Soc. (N.S.), 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8.

• Friedman, J.; Widgerson, A. (1995), "On the second eigenvalue of hypergraphs" (PDF), Combinatorica, 15 (1): 43–65, doi:10.1007/BF01294459, S2CID 17896683.