익스팬더 그래프

콤비네이터학에서 확장자 그래프는 강한 연결 특성을 가진 희소성 그래프로서 정점, 에지 또는 스펙트럼 확장을 사용하여 정량화된다.익스팬더 구조는 복잡성 이론, 강력한 컴퓨터 네트워크의 설계, 오류 수정 이론에 대한 여러 응용과 함께 순수 및 응용 수학에 대한 연구를 낳았다.^[1]

정의들

직관적으로 확장자 그래프는 "너무 크지" 않은 정점의 모든 부분집합이 "큰" 경계를 갖는 유한하고 간접적이지 않은 다중그래프다.이러한 개념의 서로 다른 공식화는 아래에 정의된 바와 같이 가장자리 확장기, 꼭지점 확장기 및 스펙트럼 확장기라는 서로 다른 개념을 야기한다.

연결된 구성요소의 경계가 비어 있으므로 연결이 끊어진 그래프는 확장기가 아니다.연결된 모든 그래프는 확장자지만 연결된 그래프마다 확장 매개변수가 다르다.전체 그래프는 확장성이 가장 좋지만 가능한 한 가장 큰 정도를 가지고 있다.비공식적으로 그래프는 낮은 도 및 높은 확장 매개변수를 가진 경우 훌륭한 확장기이다.

모서리 확장

n 정점에 있는 그래프 G의 에지 확장(등측수 또는 치거 상수도) h(G)는 다음과 같이 정의된다.

${\displaystyle h(G)=\min _{0< S \leq {\frac {n}{2}}}{\frac {\partial S}{S}},}$

where ${\displaystyle \partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\in V(G)\setminus S\}}$, which can also be written as ${\displaystyle \partial S=E(S,{\overline {S}})}$ with ${\displaystyle {\overline {S}}:=V(G)\setminus S}$the complement of ${\displaystyle S}$ and ${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}}$ the edges between the subsets of vertices ${\displaystyle A,B\subseteq V(G)}$.

방정식에서 최소값은 대부분의 n/2 정점에서의 모든 비빈 집합 S 위에 있고 andS는 S의 가장자리 경계, 즉 S에 정확히 하나의 끝점이 있는 가장자리 집합이다.^[2]

직관적으로,

${\displaystyle \min {\partial S}=\min E({S},{\overline {S})}$

그래프를 둘로 분할하기 위해 절단해야 하는 최소 에지 수입니다.가장자리 확장은 두 부분 사이의 정점 수를 최소로 나누어 이 개념을 정규화한다.정규화가 값을 크게 변경할 수 있는 방법을 보려면 다음 예를 참조하십시오.정점 수가 같은 두 개의 완전한 그래프를 선택하고 정점을 일대일로 연결하여 두 그래프 사이에 가장자리 n개를 추가한다.최소 절단은 n이 되고 가장자리 확장은 1이 된다.

Notice that in ${\displaystyle \min { \partial S }}$, the optimization can be equivalently done either over ${\displaystyle 0\leq S \leq {n}/{2}}$ or over any non-empty subset, since ${\displaystyle E({\overline {S}},{S})=E({S},{\overline {S}})$$\}\}.$ ${\displaystyle S}$ $displaystyle$S$}$에 의한 정규화$$ $때문$에 h${\displaystyle }$(${\displaystyle G}$ ) ${\displaystyle$ h$(G)}$에 대해서는 동일하지 않다$.$ 모든 비 빈 하위 집합에 대한 최적화를$$ $가지고{\displaystyle }$ h${\displaystyle }$(${\displaystyle G}$ )$${\$displaystystyle$ h$(G)}$을(G)로 다시 작성하면 된다.

${\displaystyle h(G)=\min _{S\subset V(G)}{\frac {E({S},{\overline {S}){\min\{S}{S}}}{\min\{\overline {S}}}}}}.}$

정점 확장

그래프 G의 등점수 $h{\displaystyle {}_{}}$ ${\displaystyle {\text{out}}_{}G}$) ${\displaystyle h_{\text{out}(G)}($정점 확장 또는 확대)은 다음과 같이 정의된다.

${\displaystyle h_{\text{out}}(G)=\min _{0< S \leq {\frac {n}{2}}}{\frac {\partial _{\text{out}}}}{S}}}}}$

여기서 $\partial {\displaystyle {\mathrm{}}_{\text{out}}}$(${\displaystyle S}$) ${\displaystyle \partial _{\text{out}($${\displaystyle S}$$)}$은 S의 외부 경계, 즉 ${\displaystyle V}$( G${\displaystyle }$) ${\displaystyle \setminus }$ S ${\displaystyle V(G)\setminus S}$의 정점 집합이며$$ S에는 적어도 한 개의 이웃이 있다$$.^[3]이 정의의 변종(독특한 인접 확장이라고 함)에서 $\partial {\displaystyle {\mathrm{}}_{\text{out}}}$($){\displaystyle \partial _{\text{out}(S)}$는 V의 정점 집합으로 대체되며$$ S에는 정확히 하나의 인접성이 있다.^[4]

그래프 G의${\displaystyle {}_{}}$(${\displaystyle G}$) ${\displaystyle h_{\text}}(G)$에서 ${\displaystyle {\text{등점수}}_{}}$ $h$는 다음과 같이 정의된다.

${\displaystyle h_{\text{in}}(G)=\min _{0< S \leq {\frac {n}{2}}}{\frac {\partial _{\text{in}}}}}{S}}},}$

여기서${\displaystyle {\mathrm{}}_{}}$($){\displaystyle \partial _{\text{in}($${\displaystyle S}$$)}$는 S의 내부 경계, 즉 ${\displaystyle V}$( G${\displaystyle }$) ${\displaystyle \setminus }$ S ${\displaystyle V(G)\setminus S}$에 적어도 한 개의 이웃이 있는 S의 정점 집합이다$.$^[3]

스펙트럼확장

G가 d-정규일 경우 G의 인접 행렬 A = A(G)의 고유값을 바탕으로 확장의 선형 대수적 정의가 가능하며, 여기서 ${\displaystyle {Ai}_{}}$ ${\displaystyle j_{}}$ ${\$는 정점 i와 j 사이의 에지 수입니다.^[5]Because A is symmetric, the spectral theorem implies that A has n real-valued eigenvalues ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$. It is known that all these eigenvalues are in [−d, d] and more specifically, it is known that λ_n = −d if and only if G is bipartite.

More formally, we refer to an ${\displaystyle n}$-vertex, ${\displaystyle d}$-regular graph with ${\displaystyle \max _{i\neq 1} \lambda _{i} \leq \lambda }$ as an ${\displaystyle (n,d,\lambda )}$-graph.$i{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle 1}$ ${\displaystyle$ \$lambda$ $_$${i}$에 대한${\displaystyle }$$\lambda {\displaystyle {}_{}}$ i ${\$ _{i$}$에 대한 ($n,$$lambda$$)}$ 그래픽에 의해 주어진 바운드는 확장기 혼합 보조정리기를 포함하여 여러 맥락에서 유용하다$$.

G는 정규 분포이기 때문에 모든$$${\displaystyle }$${\displaystyle i_{}}$= 1, ${\displaystyle ...}$에 대해$$u = 1 / n {\$displaystyle u_{i$$}=1/n}$이 있는 균일한 분포$$ $u{\displaystyle }$ R n {\$displaystyle$ u}=1/n$}$은 G의 고정 분포다.즉, 우리는 Au = du를 가지고 있고, u는 고유값 λ₁ = d를 가진 A의 고유 벡터(eigenvector)이며, 여기서 d는 G의 정점 수준이다.G의 스펙트럼 갭은 d - λ으로₂ 정의되며, 그래프 G의 스펙트럼 확장을 측정한다.^[6]

$\lambda {\displaystyle }$= ${\displaystyle max}$ {${\displaystyle {\lambda \mathrm{}}_{}}$ 2,${\displaystyle {}_{}\lambda {}_{}}$ ${\displaystyle n_{}}$ ${\displaystyle \}{}_{}}$ ${\displaystyle \lambda =\max\{\lambda_{2}, \lambda_{n}$ $\backslash \}\}\}\}$을(를) 설정하면 u에 직교하는 고유값에 해당하는 최대 고유값을 사용하여 동등하게 정의할 수 있다.

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\Av\ _{2}}:}$

, where

${\displaystyle \ \{2}=\left(\sum _{i=1}^{nv_{i}^{2}\오른쪽)^{1/2}}$

벡터 $v{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$의 2-노드 입니다$.$

이러한 정의의 표준화된 버전도 널리 사용되고 있으며, 일부 결과를 명시하는 데 더 편리하다.여기서는 그래프 G의 Markov 전환 행렬인 행렬 $1{\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{d}{}}$ ${\displaystyle A}$ ${\displaystyle {\tfrac {1}{d}A}$을$($를) 고려한다.그것의 고유값은 -1과 1사이에 있다.반드시 정규 그래프가 아닌 경우, 그래프의 스펙트럼은 라플라시안 행렬의 고유값을 사용하여 유사하게 정의될 수 있다.지시된 그래프의 경우 대칭 행렬 AA의^T 고유값의 뿌리와 동일한 인접 행렬 A의 단수 값을 고려한다.

서로 다른 확장 속성 간의 관계

위에서 정의한 확장 매개변수는 서로 관련되어 있다.특히 모든 d-정규 그래프 G에 대해

${\displaystyle h_{\text{out}}(G)\leq h(G)\leq d_cdot h_{\text{out})(G).}$

따라서 일정한 도 그래프의 경우 정점과 가장자리 확장은 질적으로 동일하다.

체거 불평등

언제 G{\displaystyle d}-regular, 각 꼭지점 정도 d{\displaystyle d}의 의미 d는 등주 상수 h(G)로 격차가 d− λ2 사이의 인접 연산자의 스펙트럼에서 대인 관계는 G.By표준 스펙트럼 그래프 이론d-regular 그래프의 인접 연산자는 λ1의 사소한 고유치.=d그리고 첫 번째 비파생성 고유값은₂ is이다.G가 연결되어 있으면 λ₂ < d.도쯔크에^[7] 의한 불평등과 독립적으로 알론, 밀먼은^[8] 다음과^[9] 같이 말한다.

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

사실 이런 불평등은 팽팽하다.The lower bound is achieved for the hypercube ${\displaystyle Q_{n}}$, where ${\displaystyle h(G)=1}$ and ${\displaystyle d-\lambda =2}$, while the upper bound is achieved for a cycle, where ${\displaystyle H(C_{n})=\$$Theta(1/n)$및$$ $d{\displaystyle }$ -${\displaystyle \lambda }$= ${\displaystyle \mathrm{\theta }(1}$/ ${\displaystyle n{}^{}{2\mathrm{}}^{}}$ ) ${\displaystyle d-\lambda =\theta(1/n^{2$^[1]이 불평등은 마르코프 사슬로 향하는 치거와 밀접한 관련이 있으며 리만 기하학에서 치거의 불평등을 분리하여 보여주는 것으로 볼 수 있다.

정점 등거리 수치와 스펙트럼 간격 사이의 유사한 연결도 연구되었다.^[10]

${\displaystyle h_{\text{out}(G)\leq \leq \left({4(d-\lambda _{2}}})^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2}}).}$

Asymptotically speaking, the quantities ${\displaystyle {\frac {h^{2}}{d}}}$, ${\displaystyle h_{\text{out}}}$, and ${\displaystyle h_{\text{in}}^{2}}$ are all bounded above by the spectral gap ${\displaystyle O(d-\lambda _{2})}$.

시공

익스팬더 그래프의 패밀리를 명시적으로 구성하기 위한 세 가지 일반적인 전략이 있다.^[11]첫 번째 전략은 대수학 및 집단 이뇨학, 두 번째 전략은 분석학이고 적층 결합학을 사용하며, 세 번째 전략은 결합학이며 지그재그 및 관련 그래프 제품을 사용한다.노가 알론은 유한한 기하학적 구조로 구성된 특정 그래프가 고도로 확장되는 그래프의 가장 빠른 예라는 것을 보여주었다.^[12]

마르굴리스-가버-갈릴

Cayley 그래프를 기반으로 한 대수학적 구조는 다양한 확장기 그래프로 알려져 있다.다음 건설은 마굴리스 덕분이며 가버와 갈릴이 분석했다.^[13]For every natural number n, one considers the graph G_n with the vertex set ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$, where ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$: For every vertex ${\displaystyle (x,y)\in \mathb$$b {Z} _{n}\times \mathb {Z} _{n$ 8개의 인접한 정점은

${\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${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle 5}$≤ ${\displaystyle 2\sqrt{\mathrm{}}}$ {\$displaystyle \lambda$(G)\$leq$5{\sqrt{{\$sqrt{2$

라마누잔 그래프

알론(Alon)과 보파나(Boppana)의 정리로는, 충분히 큰 모든 d-정규 그래프는 ${\displaystyle {\lambda \mathrm{}}_{}2\sqrt{}d\sqrt{}}$ -${\displaystyle \sqrt{1}}$ -${\displaystyle \mathrm{o}}$ ( 1${\displaystyle }$) ${\dplaystyle \lambda$_{2$}\sqrt{d-1-o(1)}$를 만족하며$,$ 여기서 $\lambda {\displaystyle {}_{}}$ ${\$ \lamba $_{{{{{{{{{{{2$}는$$ 절대값으로 두 번째로 큰 고유값이다.^[14]그 직접적인 결과로, 우리는 모든 고정 $d{\displaystyle }$ ${\디스플레이 스타일$ d$}$ 및 fixed$$ < -1 ${\$ $스타일 \lambda <2{\sqrt${\sqrt${\displaystyle \{\mathrm{d-1}}$$}}}$에 대해 미세하게 많은${\displaystyle }$($n, d,\lambda )}$ -그래프만$$ 존재한다는 것을 알고 있다.Ramanujan 그래프다d-regular 그래프 이 튀어 달린대요 λ 나는 <)λ max을 만족시키기, dλ 나는 ≤ 2d− 1{\displaystyle \lambda =\max_{\lambda_{나는}<>d}\lambda _{나는}\leq 2{\sqrt{d-1}}}.[15]따라서Ramanujan 그래프 λ 2의 점근적으로 가능한 한 작게 가치를 가지고 있{\displaystyle \lam.bda _{2}}$$이것은 그들을 훌륭한 스펙트럼 확장기로 만든다.

루보츠키, 필립스, 사르낙(1988), 마굴리스(1988), 모르겐스턴(1994) 등은 라마누잔 그래프를 어떻게 명시적으로 구성할 수 있는지를 보여준다.^[16]

1985년 Alon은 n 정점에 대한 $대부분$의 d ${\displaystyle d}-$정규$$ 그래프가 $충분히{\displaystyle }$ 큰 n ${\displaystyle n$에 대해 거의 라마누잔이라고 추측했다.^[17]즉, > ${\displaystyle \varepsilon >0}$에 대해서는 만족한다

${\displaystyle \lambda }$ ${\displaystyle \le }$ 2 ${\displaystyle \sqrt{\mathrm{d}}}$ -${\displaystyle \sqrt{}}$1${\displaystyle }$+ ${\displaystyle \epsilon }$ ${\displaystyle$\ \$da \leq$ 2${\sqrt{d-1}+\varepsilon$$}.$

2003년, 조엘 프리드먼과 무엇을 의미한다"대부분의 d{\displaystyle d}-regular 그래프"에 의해 무작위d-regular 그래프마다 ε 을에 ≤ 2d− 1+ε{\displaystyle \lambda \leq 2{\sqrt{d-1}}+\varepsilon}λ는지 보여 줍니다.에 의해 지정된;확률 1과 0{\displaystyle \varepsilon>0}O(−은 추측을 증명했다.nτ${\displaystyle {}^{})}$ ${\displaystyle 1-O(n^{\tau$ $\},$ 여기서 $where{\displaystyle }$= ${\displaystyle \lceil (\mathrm{d}\sqrt{}}$- ${\displaystyle \sqrt{1}}$+${\displaystyle }$1)${\displaystyle }$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rceil }$ ${\displaystyle \tau =\lceil({\sqrt{d-1}+1)/2\rceil$ $\}.$^[18][19]

지그재그 제품

레이놀드, 바단, 위그더슨은 2003년에 지그재그 제품을 선보였다.^[20]대략적으로, 두 개의 익스팬더 그래프의 지그재그 제품은 약간 더 심한 확장만을 가진 그래프를 만들어낸다.따라서 지그재그 제품은 확장기 그래프의 패밀리를 구성하는 데도 사용될 수 있다.If ${\displaystyle G}$ is a ${\displaystyle (n,m,\lambda _{1})}$-graph and ${\displaystyle H}$ is an ${\displaystyle (m,d,\lambda _{2})}$-graph, then the zig-zag product ${\displaystyle G\circ H}$ is a ${\displaystyle$$(nm,d^{2},\varphi(\boda _{1},\bodda \{2})}$ -그래프$$ ${\displaystyle \varphi }$은(는) 다음과 같은 속성을 가지고$$ 있다.

1. 1 < $>$ <<\$displaystyle \lambda _$${1}>,$ 2$<{2}>,$φ ( , 2)< $<<\displaystyle \varphi$(\$lambda _{1},\lambda _{2$
2. ${\displaystyle \phi }$ (${\displaystyle {\lambda \mathrm{}}_{}}$ 1,${\displaystyle {}_{}{\lambda \mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle \le }$ 1 +${\displaystyle {}_{}{\lambda \mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$ (\ ($da _{1},\},da _${2$})\leq$\ \$da _{1}+\+$da$_{2$

Specifically, ${\displaystyle f(\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}}$.^[20]

속성(1)은 두 확장자 그래프의 지그재그 제품도 확장자 그래프임을 의미하므로, 지그재그 제품을 유도적으로 사용하여 확장자 그래프 패밀리를 만들 수 있다.

직감적으로 지그재그 제품의 구성은 다음과 같은 방법으로 생각할 수 있다.$G{\displaystyle }$ ${\displaystyle G}$의 각 꼭지점은 정점에 연결된 다른 가장자리와 연결된 m 꼭지점의 "클라우드"로 폭파된다$$.Each vertex is now labeled as ${\displaystyle (v,k)}$ where ${\displaystyle v}$ refers to an original vertex of ${\displaystyle G}$ and ${\displaystyle k}$ refers to the ${\displaystyle k}$th edge of ${\displaystyle v}$. Two vertices, ${\displaystyle (v,k)}$ and ${\displaystyle (w,l)}$$$다음과 같은 이동 순서를 통해$$ $({\displaystyle v}$, k${\displaystyle }$) ${\displaystyle (v,k)}$에서${\displaystyle }$( ${\displaystyle w}$, l${\displaystyle }$) ${\displaystyle (w,l)}($으)로$$ 이동할 수 있는 경우 ${\displaystyle ($w,l$)}$이(가) 연결된다$$.

1. Zig - $H{\displaystyle }$ ${\displaystyle H}$의 가장자리를 사용하여${\displaystyle }$$($${\displaystyle v}$, k${\displaystyle }$) ${\displaystyle(v,k')}$에서${\displaystyle }$(${\displaystyle {}^{},}$${\displaystyle k}$${\displaystyle {)\}(}^{}}$으)로 이동하십시오$.$
2. $G$ ${\displaystyle G}$의 에지 $k{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ k$'}$을(를${\displaystyle {)}^{}}$ 사용하여 클라우드를 건너뛰어$displaystyle(w,l')$로 이동하십시오.$}$
3. Zag - $H{\displaystyle }$ ${\displaystyle H}$의 가장자리를 사용하여$$ $({\displaystyle w}$, l ${\displaystyle {\prime }^{}}$) ${\$displaystyle$(w,l')}$에서${\displaystyle }$( ${\displaystyle w}$, l${\displaystyle }$) ${\displaystyle(w,l)}($으)로 이동하십시오$.$^[20]

랜덤화 시공

확률론적 주장을 통해 확장성이 좋은 그래프의 존재를 보여주는 결과가 많다.사실, 증량제의 존재를 처음 Pinsker[21]에 의해 그분께서 randomly 선택한 n{n\displaystyle}꼭지점을 위해 정기적으로 양분 그래프{\displaystyle d}d을 떠나 입증되었다, Nvertices Scdn{\displaysty ≤ 모든 하위 집합을≥(d− 2)S{\displaystyle N(S)\geq(d-2)S}(S).르S(c_{d}n} 높은 확률은 O(d− 4){O(d^{4})\displaystyle}. Alon과 Roichman[22]모든 그룹에서 주문 n{n\displaystyle}의 G{G\displaystyle}과 매 1>는 있는 cd{\displaystyle c_{d}}은 일정한 d에 따라{\displaystyle d};ε>0{\di.splaystylE1>, \varepsilon<>를 사용하여 0}일 경우, 약간의 c(ε)>은 0{\displaystyle c(\varepsilon)>0}은 G{G\displaystyle}에 c(ε)로그 2⁡ n{\displaystyle c(\varepsilon)\log_{2}n}발전기로 케일리 그래프는ε{\displaystyle \varepsilon}확장기, 즉 2등을 고유치 1이하의− ε.{\display$스타일 1-\barepsilon$ $\},$ 높은 확률로.

응용 프로그램 및 유용한 속성

익스팬더에 대한 원래 동기는 경제적인 견고한 네트워크 구축(전화 또는 컴퓨터)이다. 한정된 용맹을 가진 익스팬더는 모든 서브셋에 대해 크기(정점 수)에 따라 선형적으로 증가하는 가장자리 수를 가진 점증적 강력한 그래프를 정확하게 나타낸다.

익스팬더 그래프는 컴퓨터 과학, 알고리즘 설계, 코드 수정 오류, 추출기, 가성 생성기, 분류 네트워크(Ajtai, Komloss & Szemerédi(1983) 및 강력한 컴퓨터 네트워크 등에서 광범위한 응용 분야를 발견했다.그것들은 또한 SL = L (Reingold (2008)과 PCP 정리 (Dinur (2007))와 같은 계산 복잡성 이론에서 많은 중요한 결과의 입증에도 사용되었다.암호학에서는 해시함수를 구성하는 데 익스팬더 그래프를 사용한다.

2006년 익스팬더 그래프 조사에서 호리, 라이니얼, 위그더슨은 익스팬더 그래프 연구를 극단적 문제, 전형적인 행동, 명시적 구성, 알고리즘의 4가지 범주로 나눴다.극단적 문제는 확장 매개변수의 경계에 초점을 맞추는 반면, 일반적인 행동 문제는 확장 매개변수가 랜덤 그래프에 걸쳐 분포되는 방식을 특징으로 한다.명시적 구성은 특정 매개변수를 최적화하는 그래프를 구성하는 데 초점을 맞추고 알고리즘 질문은 매개변수의 평가와 추정을 연구한다.

익스팬더 혼합 보조정리

익스팬더 혼합 보조정리에서는${\displaystyle }$(${\displaystyle n}$, ${\displaystyle d}$ ,${\displaystyle \lambda }$) ${\dapplaystyle (n,d,\lambda )}$ -그래프의$$ 경우, 정점 S, T ⊆ V의 어떤 두 하위 집합에 대해 S와 T 사이의 에지 수는 대략 랜덤 d-정규 그래프에서 예상할 수 있는 값이라고 명시한다.근사치는 $\lambda {\displaystyle }$ ${\displaystyle \lambda }$이(가) 작을수록$$ 좋다.무작위 d-정규 그래프뿐만 아니라 에지 확률 d/n이 있는 Erdss-Rényi 랜덤 그래프에서도 S와 T 사이의 에지 d${\displaystyle }$edges$$ S ${\displaystyle edges}$ T $dfrac {d}{n}}\cdot$S$\cdot$T$}$를 예상한다.

좀 더 형식적으로 E(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}}}.}$

$({\displaystyle n}$, ${\displaystyle d}$ ,${\displaystyle \lambda }$) ${\displaystyle (n,d,\lambda )}$ -그래프의$$ 많은 속성은 다음을 포함하여 확장기 혼합 레마의 산호관이다.^[1]

• 그래프의 독립적인 집합은 정점이 두 개 인접하지 않은 정점의 부분집합이다.$({\displaystyle n}$, ${\displaystyle d}$ ,${\displaystyle \lambda }$) ${\displaystyle (n,d,\lambda )}$ -그래프에서$$ 독립 집합의 크기는 최대 $most{\displaystyle }$ ${\displaystyle n}$/ ${\displaystyle d}$ ${\displaystyle \lambda n/d}$이다$.$
• 그래프 $G{\displaystyle }$ ${\displaystyle G},$$\chi {\displaystyle }$ ${\displaystyle (G}$ ${\displaystyle )}$ ${\displaystyle \chi (G$의 색상은 인접한 정점들이 다른 색을 갖도록 필요한 최소 색 수입니다.Hoffman showed that ${\displaystyle d/\lambda \leq \chi (G)}$,^[23] while Alon, Krivelevich, and Sudakov showed that if ${\displaystyle d<2n/3}$, then ${\displaystyle \chi (G)\leq O(d/\log(1+d/\lambda ))}$.^[24]
• 그래프의 직경은 두 꼭지점 사이의 최대 거리로, 두 꼭지점 사이의 거리는 그들 사이의 최단 경로로 정의된다.${\displaystyle 정}$ 교수는 ${\displaystyle \mathrm{그래픽}}$의$직경$이 최대 $\lceil {\displaystyle }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle n/\log }$ log${\displaystyle (d/\backslash lambda}$$$${\displaystyle )\backslash }$rceil $daystyle \log n/\log(d/\lambda )\rceil$^[25]$}$

익스팬더 워크 샘플링

Chernoff 바운드는 [-1, 1] 범위의 랜덤 변수에서 많은 독립적인 표본을 추출할 때 높은 확률로 표본의 평균이 랜덤 변수의 예상에 가깝다고 명시한다.아제타이, 콤로스 & 스제메르디(1987년), 길만(1998년)으로 인해 확장자 보행시료 채취 보조마사는 확장자 그래프에서 보행시료 채취 시에도 이 점이 유효하다고 언급하고 있다.이것은 특히 디랜도메이션 이론에서 유용하다. 확장자 보행에 따른 샘플링은 독립적으로 샘플링하는 것보다 훨씬 적은 수의 랜덤 비트를 사용하기 때문이다.

AKS 정렬 네트워크 및 대략적인 Halvers

정렬 네트워크는 입력 집합을 취하며 입력들을 정렬하기 위해 일련의 병렬 단계를 수행한다.병렬 단계는 임의의 수의 분리 비교를 수행하고 비교 입력 쌍을 교환하는 것으로 구성된다.네트워크의 깊이는 그것이 취하는 병렬 단계의 수에 의해 주어진다.익스팬더 그래프는 깊이 $O{\displaystyle (\mathrm{로그}}$ ${\displaystyle n}$) ${\displaystyle$ O$(\log n)}$을 달성하는 AKS 정렬 네트워크에서 중요한 역할을 한다$.$ 이 그래프는 점증적으로 정렬 네트워크에 대해 가장 잘 알려진 깊이인 반면, 익스팬더에 대한 의존도는 상수 바인딩을 실제 사용하기에 너무 크게 만든다.

AKS 정렬 네트워크 내에서 익스팬더 그래프를 사용하여 경계 깊이 $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon}$ -halvers를$$ 구성한다.An ${\displaystyle \varepsilon }$-halver takes as input a length ${\displaystyle n}$ permutation of ${\displaystyle (1,\ldots ,n)}$ and halves the inputs into two disjoint sets ${\displaystyle A}$ and ${\displaystyle B}$ such that for each integer ${\displaystyle k\leq n/2}$ at$k{\displaystyle }$ ${\displaystyle k}$ 최소$$ 입력 중 ${\displaystyle \mathrm{most}}$ k ${\displaystyle$ $\varepsilon$ k$}$은(는) $대부분{\displaystyle }$ B ${\displaystyle$ B$}$에 있으며, $최대$ ${\displaystyle \mathrm{입력}}$$$ inputs$$ $k{\displaystyle }$ ${\displaystyle$ k$}$은(는$)$ A {\$displaystystystyle$ A$}$에 있다$.$$A{\displaystyle }$$$ ${\displaystyle A}$ 및$$ $B{\displaystyle }$ ${\displaystyle B}$ 세트는$\epsilon {\displaystyle }$ {\$displaystyle \varepsilon}$ -halving이다$$.

아제타이, 콤일로스 & 스제메레디(1983)에 이어 깊이 $d{\displaystyle }$ ${\displaystyle d}$${\displaystyle }$ ${\displaystyle \varepsilon }$ -halver를$$ 다음과 같이 시공할 수 있다.Take an ${\displaystyle n}$ vertex, degree ${\displaystyle d}$ bipartite expander with parts ${\displaystyle X}$ and ${\displaystyle Y}$ of equal size such that every subset of vertices of size at most ${\displaystyle \varepsilon n}$ has at least ${\displaystyle {\frac {1-\varepsilon }{\$$바렙실론 }}}$의 이웃들.

그래프의 정점은 입력을 포함하는 레지스터로 생각할 수 있고 가장자리는 두 레지스터의 입력을 비교하는 와이어로 생각할 수 있다.시작 시 $입력$의$$절반은 X {\$displaystyle X}$에, $절반$은 Y ${\displaystyle Y}$에 임의로 배치하고$$ 가장자리를 $d{\displaystyle }$ ${\displaystyle d}$완벽$$ 일치로 분해하십시오.목표는 입력의 작은 절반을 대략적으로$$ $포함$하는 X ${\displaystyle$ X$}$과 입력의 큰 절반을$$ $포함$하는$$Y {\$displaystyle Y}$로 끝나는 것이다.이를 위해 이 일치의 가장자리와 짝을 이룬 레지스터를 비교하여 각 일치를 순차적으로 처리하고 순서가 잘못된 입력을 수정하십시오.특히 매칭의 각 에지에 대해, 큰 입력이 $X{\displaystyle }$ ${\displaystyle$ X$}$의 레지스터에 있고 작은$$ 입력이 Y ${\displaystyle Y}$의 레지스터에 있다면$,$ 작은 입력이 $X{\displaystyle }$ ${\displaystyle$ $X$$}$에 있고 큰 입력이 $Y{\displaystyle }$ ${\displaysty$ Y$}$에 있도록 두 입력을 교환한다$.$oecess는 $d{\displaystyle }$ ${\displaystyle d}$개의$$ 평행 단계로 구성된다.

모든 $d{\displaystyle }$ ${\displaystyle d}$ 라운드$$ 후에 $A{\displaystyle }$ ${\displaystyle A}$을(를) $X{\displaystyle }$ ${\displaystyle X}$의 레지스터에 있는 입력 집합으로, $B$ ${\displaystyle Y}$의 레지스터에 있는 $입력$ 집합으로 가져와 $\epsilon$ ${\displaystyle \varpsilon }$ -halving을$$ 얻으십시오.이를 확인하려면 $X{\displaystyle }$ ${\displaystyle X$$}$의 레지스터 $u{\displaystyle }$ ${\displaystyle$ $u$$}$과($와$) $Y{\displaystyle }$ ${\displaystyle$ y}의 v {\displaystyle $v}$이(가) 에지 ${\displaystyle \mathrm{uv}}$ ${\$displaysty $u}$에 연결된 경우$$$$$이{\displaystyle }$ 에지와 $일치$하는 후$u$ {\displaystystystytemput이(가 $v$의 입력보다 작다는$$ 점에 유의하십시오.$또한$ 이$$속성은 나머지 과정에서도 그대로 유지된다$.$Now, suppose for some ${\displaystyle k\leq n/2}$ that more than ${\displaystyle \varepsilon k}$ of the inputs ${\displaystyle (1,\ldots ,k)}$ are in ${\displaystyle B}$. Then by expansion properties of the graph, the registers of these inputs in ${\displaystyle Y}$ are connected with$적어도$ $1{\displaystyle \frac{\mathrm{}}{}}$ -${\displaystyle \frac{\epsilon }{}}$ ${\displaystyle \frac{}{}}$ ${\displaystyle k}$ ${\displaystyle {\frac {1-\varepsilon }{\varepsilon }k$$\}$ 레지스터가$$ $X{\displaystyle }$ ${\\displaystyle$ X$}$에 추가되므로 $일부{\displaystyle }$ $레지스터{\displaystyle }$ b ${\displaystytle X$$}$에 $연결$된 레지스터가 있어야 $한다$.${\displaystyle a}$의 최종 입력이 (${\displaystyle 1}$, $\dots {\displaystyle }$ ,${\displaystyle }$k${\displaystyle }$) ${\displaystyle (1,\ldots ,k$에 있지$$ 않도록 Y ${\displaystyle Y}$에서 $}$ ${\$displaystyle $b}$의 최종 입력이 b ${\displaystyle \{\backslash }$$displaystystyle$ b}에$$ 없음그러나 이는 이전 속성을 위반하므로 출력 세트 A ${\displaystyle A}$ $및$ B ${\displaystyle B}$은(는) $\epsilon {\displaystyle }$ ${\displaystyle \varepsilon}$ -halving이어야$$ 한다$$.

참고 항목

• 대수연결성
• 지그재그 제품
• 슈퍼스트롱 근사치
• 스펙트럼 그래프 이론

메모들

참조

외부 링크

• 미국수학협회의 통지에 대한 간략한 소개
• 마이클 닐슨 소개서
• 확장자에 대한 강의 노트(Nati Linial 및 Avi Wigderson)
• 확장자에 대한 강의 노트(Prahladh Harsha)
• 스펙트럼 격차의 정의 및 적용