Gráfico expansor

AjustarCompartirImprimirCitar

Gráfico esparso com conectividade forte

Na teoria dos grafos, um gráfico expansor é um grafo esparso que possui fortes propriedades de conectividade, quantificadas usando vértice, aresta ou expansão espectral. As construções do expansor geraram pesquisas em matemática pura e aplicada, com várias aplicações para a teoria da complexidade, projeto de redes robustas de computadores e a teoria dos códigos de correção de erros.

Definições

Intuitivamente, um grafo expansor é um multigrafo finito e não direcionado no qual cada subconjunto dos vértices que não é "muito grande" tem um "grande" limite. Diferentes formalizações dessas noções dão origem a diferentes noções de expansores: expansores de arestas, expansores de vértices e expansores espectrais, conforme definido abaixo.

Um gráfico desconectado não é um expansor, pois o limite de um componente conectado está vazio. Todo grafo conectado é um expansor; no entanto, diferentes gráficos conectados têm diferentes parâmetros de expansão. O grafo completo tem a melhor propriedade de expansão, mas tem o maior grau possível. Informalmente, um grafo é um bom expansor se tiver parâmetros de baixo grau e alto de expansão.

Expansão de borda

A expansão da aresta (também número isoperimétrico ou constante de Cheeger) $h (G)$ de um gráfico $G$ em $n$ vértices é definido como

<math alttext="{displaystyle h(G)=min _{0h(G)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =min0<|S|≤ ≤ n2|∂ ∂ S||S|,{displaystyle h(G)=min _{0<|S|leq {frac Não. {|partial S|}{|S|}},}<img alt="h(G)=min _{0

Onde?

{displaystyle partial S:={{u,v}in E(G): uin S,vin V(G)setminus S},}

que também pode ser escrito como $\partial S = E (S, S)$ com $S := V (G) S$ o complemento de $S$ e

{displaystyle E(A,B)={{u,v}in E(G): uin A,vin B}}

as arestas entre os subconjuntos de vértices $A, B \subseteq V (G)$ .

Na equação, o mínimo é sobre todos os conjuntos não vazios $S$ de no máximo $n ⁄ 2$ vértices e $\partial S$ é o limite da aresta de $S$ , ou seja, o conjunto de arestas com exatamente uma extremidade em $S$ .

Intuitivamente,

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

é o número mínimo de arestas que precisam ser cortadas para dividir o gráfico em dois. A expansão de borda normaliza esse conceito dividindo com o menor número de vértices entre as duas partes. Para ver como a normalização pode alterar drasticamente o valor, considere o exemplo a seguir. Pegue dois grafos completos com o mesmo número de vértices $n$ e adicione $n$ arestas entre os dois grafos conectando seus vértices um a um. O corte mínimo será $n$ mas a expansão da borda será 1.

Observe que $min | \partial S |$ , a otimização pode ser feita de forma equivalente $0 \leq | S | \leq n ? 2$ ou sobre qualquer subconjunto não vazio, desde ${displaystyle E(S,{overline {S}})=E({overline {S}},S)}$ . O mesmo não é verdade para $h (G)$ por causa da normalização por $| S |$ . Se quisermos escrever $h (G)$ com uma otimização sobre todos os subconjuntos não vazios, podemos reescreve-lo como

{displaystyle h(G)=min _{emptyset subsetneq Ssubsetneq V(G)}{frac {E({S},{overline {S}})}{min{|S|,|{overline {S}}|}}}.}

Expansão do vértice

O número isoperimétrico do vértice $h saída (G)$ (também expansão do vértice ou ampliação) de um gráfico $G$ é definido como

<math alttext="{displaystyle h_{text{out}}(G)=min _{0hfora(G)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =min0<|S|≤ ≤ n2|∂ ∂ fora(S)||S|,{displaystyle h_{text{out}}(G)=min _{0<|S|leq {frac {n}{2}}}{frac {|partial _{text{out}}(S)|}{|S|}},}<img alt="h_{text{out}}(G)=min _{0

onde $\partial out (S)$ é o limite externo da $S$ , ou seja, o conjunto de vértices em $V (G) S$ com pelo menos um vizinho em $S$ . Em uma variante dessa definição (chamada expansão de vizinho único) $\partial out (S)$ é substituído pelo conjunto de vértices em $V$ com exatamente um vizinho em $S$ .

O número isoperimétrico do vértice $h in (G)$ de um gráfico $G$ é definido como

<math alttext="{displaystyle h_{text{in}}(G)=min _{0hem(G)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =min0<|S|≤ ≤ n2|∂ ∂ em(S)||S|,{displaystyle h_{text{in}}(G)=min _{0<|S|leq {frac Não. {|partial _{text{in}}(S)|}{|S|}},}<img alt="h_{text{in}}(G)=min _{0

Onde? $partial _{text{in}}(S)$ é o fronteira interna de $S$ , i.e., o conjunto de vértices em $S$ com pelo menos um vizinho em $V (G) S$ .

Expansão espectral

Quando $G$ é d-regular, uma definição algébrica linear de expansão é possível com base nos autovalores da matriz de adjacência $A = A (G)$ de $G$ , onde $A ij$ é o número de arestas entre os vértices $i$ e $j$ . Como $A$ é simétrico, o teorema espectral implica que $A$ tem $n$ autovalores de valor real $λ 1 \geq λ 2 \geq \dots \geq λ n$ . Sabe-se que todos esses autovalores estão em $[- d, d]$ e mais especificamente, sabe-se que $λ n = - d$ se e somente se estilo $G$ é bipartido.

Mais formalmente, nos referimos a um $n$ -vertex, $d$ -gráfico regular com

{displaystyle max _{ineq 1}|lambda _{i}|leq lambda }

como um $(n, d, λ)$ -gráfico. O limite dado por um gráfico $(n, d, λ)$ em $λ i$ para $i \neq 1$ é útil em muitos contextos, incluindo o expansor lema de mistura.

Porque... $G$ é regular, a distribuição uniforme $uin mathbb {R} ^{n}$ com $u Eu... = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1 ? n$ para todos $Eu... 1,..., n$ é a distribuição estacionária de $G$ . Isso é, nós temos $Au! = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = du du du du$ e $u$ é um eigenvector de $A$ com valor de eigen $λ 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = D$ , onde $D$ é o grau dos vértices de $G$ . O gap espectral de $G$ é definido como $D - Sim. 2$ , e mede a expansão espectral do gráfico $G$ .

Se definirmos

{displaystyle lambda =max{|lambda _{2}|,|lambda _{n}|}}

como este é o maior autovalor correspondente a um autovetor ortogonal para $u$ , pode ser definido de forma equivalente usando o quociente de Rayleigh:

lambda =max _{vperp u,vneq 0}{frac {|Av|_{2}}{|v|_{2}}},

onde

|v|_{2}=left(sum _{i=1}^{n}v_{i}^{2}right)^{1/2}

é o 2-norm do vetor $vin mathbb {R} ^{n}$ .

As versões normalizadas dessas definições também são amplamente usadas e mais convenientes para apresentar alguns resultados. Aqui se considera a matriz $1 / d A$ , que é a matriz de transição de Markov do gráfico $G$ . Seus autovalores estão entre −1 e 1. Para grafos não necessariamente regulares, o espectro de um gráfico pode ser definido similarmente usando os autovalores da matriz Laplaciana. Para grafos direcionados, considera-se os valores singulares da matriz de adjacência $A$ , que são iguais às raízes dos autovalores do simétrico matriz $A T A$ .

Relações entre diferentes propriedades de expansão

Os parâmetros de expansão definidos acima estão relacionados entre si. Em particular, para qualquer gráfico $d$ -regular $G$ ,

h_{text{out}}(G)leq h(G)leq dcdot h_{text{out}}(G).

Consequentemente, para grafos de grau constante, a expansão de vértices e arestas são qualitativamente iguais.

Desigualdades Cheeger

Quando $G$ é $d$ -regular, significando que cada vértice é de grau $d$ , existe uma relação entre a constante isoperimétrica $h (G)$ e a lacuna $d - λ 2$ no espectro do operador de adjacência de $G$ . Pela teoria padrão dos grafos espectrais, o autovalor trivial do operador de adjacência de um grafo $d$ -regular é $λ 1 = d$ e o primeiro autovalor não trivial é $λ 2 . Se G estiver conectado, então λ 2 < d . Uma desigualdade devido a Dodziuk e independentemente Alon e Milman afirma que$

{tfrac {1}{2}}(d-lambda _{2})leq h(G)leq {sqrt {2d(d-lambda _{2})}}.

Na verdade, o limite inferior é apertado. O limite inferior é alcançado no limite para o hipercubo $Q n$ , onde $h (G) = 1$ e $D - λ = 2$ . O limite superior é (assintoticamente) alcançado para um ciclo, onde $H. H. H. (C n) = 4/ n Θ(1/) n)$ e $pi$ . Um limite melhor é dado como

{displaystyle h(G)leq {sqrt {d^{2}-lambda _{2}^{2}}}.}

Essas desigualdades estão intimamente relacionadas ao limite de Cheeger para cadeias de Markov e podem ser vistas como uma versão discreta da desigualdade de Cheeger na geometria Riemanniana.

Conexões semelhantes entre números isoperimétricos de vértices e a lacuna espectral também foram estudadas:

h_{text{out}}(G)leq left({sqrt {4(d-lambda _{2})}}+1right)^{2}-1

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

Assintoticamente falando, as quantidades $h 2 ⁄ d$ , $h fora$ e $h entrada 2$ são todos limitados acima pelo gap espectral $O (d - λ 2)$ .

Construções

Existem três estratégias gerais para construir explicitamente famílias de grafos expansores. A primeira estratégia é algébrica e teórica de grupos, a segunda estratégia é analítica e usa combinatória aditiva, e a terceira estratégia é combinatória e usa o zig-zag e produtos gráficos relacionados. Noga Alon mostrou que certos grafos construídos a partir de geometrias finitas são os exemplos mais esparsos de grafos altamente expansíveis.

Margulis–Gabber–Galil

Construções algébricas baseadas em gráficos de Cayley são conhecidas por várias variantes de gráficos expansores. A seguinte construção deve-se a Margulis e foi analisada por Gabber e Galil. Para cada número natural $n$ , um considera o gráfico $G n$ com o conjunto de vértices $mathbb {Z} _{n}times mathbb {Z} _{n}$ , onde $mathbb {Z} _{n}=mathbb {Z} /nmathbb {Z}$ : Para cada vértice $(x,y)in mathbb {Z} _{n}times mathbb {Z} _{n}$ , seus oito vértices adjacentes são

(xpm 2y,y),(xpm (2y+1),y),(x,ypm 2x),(x,ypm (2x+1)).

Então vale o seguinte:

Theorem. Para todos $n$ , o gráfico $G n$ tem o segundo maior valor de eigen $lambda (G)leq 5{sqrt {2}}$ .

Gráficos de Ramanujan

Por um teorema de Alon e Boppana, todos suficientemente grandes $D$ - grafos regulares satisfazem ${displaystyle lambda _{2}geq 2{sqrt {d-1}}-o(1)}$ , onde $λ 2$ é o segundo maior valor de eigen em valor absoluto. Como consequência direta, sabemos que para cada fixo $D$ e $<math alttext="{displaystyle lambda λ λ <2D- Sim. - Sim. 1{displaystyle lambda <2{sqrt {d-1}}} <img alt="{displaystyle lambda$ há apenas finitamente muitos $(n, D, λ)$ -gramas. Gráficos de Ramanujan são $D$ - gráficos regulares para os quais este limite é apertado, satisfazendo

<math alttext="{displaystyle lambda =max _{|lambda _{i}|λ λ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =máx.|λ λ Eu...|<D|λ λ Eu...|≤ ≤ 2D- Sim. - Sim. 1.{displaystyle lambda =max _{|lambda _{i}|<d}|lambda _{i}|leq 2{sqrt {d-1}}}<img alt="{displaystyle lambda =max _{|lambda _{i}|

Portanto, os gráficos de Ramanujan têm um valor assintoticamente menor possível de $λ 2$ . Isso os torna excelentes expansores espectrais.

Lubotzky, Phillips e Sarnak (1988), Margulis (1988) e Morgenstern (1994) mostram como os gráficos de Ramanujan podem ser construídos explicitamente.

Em 1985, Alon, conjecturou que a maioria $d$ -gráficos regulares em $n$ vértices, para $n$ suficientemente grandes, são quase Ramanujan. Ou seja, para $φ > 0$ , eles satisfazem

{displaystyle lambda leq 2{sqrt {d-1}}+varepsilon }

Em 2003, Joel Friedman ambos provaram a conjectura e especificou o que significa "mais $D$ - gráficos regulares" mostrando que os gráficos d-regulares aleatórios têm ${displaystyle lambda leq 2{sqrt {d-1}}+varepsilon }$ para todos $φ > 0$ com probabilidade $1 - O (n ?)$ , onde

{displaystyle tau =leftlceil {frac {{sqrt {d-1}}+1}{2}}rightrceil.}

Produto Zig-Zag

Reingold, Vadhan e Wigderson introduziram o produto zig-zag em 2003. Grosso modo, o produto zig-zag de dois gráficos expansores produz um gráfico com expansão apenas um pouco pior. Portanto, um produto zig-zag também pode ser usado para construir famílias de grafos expansores. Se $G$ for um $(n, m, λ 1)$ -graph e $H$ é uma classe (m, d, λ₁)-graph, então o produto zig-zag $G ◦ H$ é um $(nm, d 2, φ (λ 1, λ 2))$ -gráfico onde $φ$ tem as seguintes propriedades.

Se $λ 1 < 1$ e $λ 2 < 1$ , então $φ (em inglês) 1, λ 2 < 1$ ;
$φ (em inglês) 1, λ 2) \leq λ 1 + λ 2$ .

Especificamente,

{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}+4lambda _{2}^{2}}}.}

Observe que a propriedade (1) implica que o produto em zigue-zague de dois gráficos de expansão também é um gráfico de expansão, portanto, produtos em zigue-zague podem ser usados indutivamente para criar uma família de gráficos de expansão.

Intuitivamente, a construção do produto zig-zag pode ser pensada da seguinte maneira. Cada vértice de $G$ é ampliado para uma "nuvem" de $m$ vértices, cada um associado a uma aresta diferente conectada ao vértice. Cada vértice agora é rotulado como $(v, k)$ onde $v$ refere-se a um vértice original de $G$ e $k$ refere-se à $k$ ª borda da $v$ . Dois vértices, $(v, k)$ e $(w, l)$ estão conectados se for possível obter de $(v, k)$ para $(w, l)$ através da seguinte sequência de movimentos.

Zig. - Afasta-te. $(v, k)$ para $(v, k ')$ , usando uma borda de $H. H. H.$ .
Saltar em nuvens usando borda $k '$ em $G$ para começar $(O quê?, Eu... ')$ .
Zag - Afasta-te. $(O quê?, Eu... ')$ para $(O quê?, Eu...)$ usando uma borda de $H. H. H.$ .

Construções aleatórias

Existem muitos resultados que mostram a existência de grafos com boas propriedades de expansão através de argumentos probabilísticos. De fato, a existência de expansores foi provada pela primeira vez por Pinsker, que mostrou que, para um $n$ vértice esquerdo $d$ gráfico bipartido regular, $| N (S) | \geq (d - 2)| S |$ para todos os subconjuntos de vértices $| S | \leq c d n$ com alta probabilidade, onde $c d$ é uma constante dependendo de $d$ que é $O (d -4)$ . Alon e Roichman mostraram que para cada grupo $G$ de ordem $n$ e a cada $1 > ε > 0$ , há algum $c (ε) > 0$ tal que o gráfico de Cayley em $G$ com $c (ε) log 2 n$ geradores é um $ε$ expansor, ou seja, tem segundo autovalor menor que $1 - ε$ , com alta probabilidade.

Aplicativos e propriedades úteis

A motivação original para expansores é construir redes econômicas robustas (telefone ou computador): um expansor com grau limitado é precisamente um grafo robusto assintótico com o número de arestas crescendo linearmente com o tamanho (número de vértices), para todos os subconjuntos.

Gráficos expansores encontraram extensas aplicações em ciência da computação, na concepção de algoritmos, códigos de correção de erros, extratores, geradores pseudo-aleatórios, redes de classificação (Ajtai, Komlós & Szemerédi (1983)) e redes robustas de computadores. Eles também foram usados em provas de muitos resultados importantes na teoria da complexidade computacional, como SL = L (Reingold (2008)) e o teorema PCP (Dinur (2007)). Na criptografia, gráficos expansores são usados para construir funções de hash.

Em uma pesquisa de 2006 sobre gráficos de expansão, Hoory, Linial e Wigderson dividiram o estudo de gráficos de expansão em quatro categorias: problemas extremos, comportamento típico, construções explícitas e algoritmos. Os problemas extremos concentram-se na delimitação dos parâmetros de expansão, enquanto os problemas típicos de comportamento caracterizam como os parâmetros de expansão são distribuídos em gráficos aleatórios. As construções explícitas se concentram na construção de gráficos que otimizam determinados parâmetros, e as questões algorítmicas estudam a avaliação e estimativa de parâmetros.

Lema de mistura do expansor

O lema da mistura do expansor afirma que para um gráfico $(n, d, λ)$ , para quaisquer dois subconjuntos dos vértices $S, T \subseteq V$ , o número de arestas entre $S$ e $T$ é aproximadamente o que você esperaria em um gráfico aleatório $d$ -regular. A aproximação é melhor quanto menor for $λ$ . Em um grafo aleatório $d$ -regular, bem como em um grafo aleatório Erdős–Rényi com probabilidade de borda $d ⁄ n$ , esperamos $d ⁄ n • | S | • | T |$ arestas entre $S$ e $T$ .

Mais formalmente, deixe $E (S, T)$ denotar o número de arestas entre $S$ e $T$ . Se os dois conjuntos não são disjuntos, as arestas em sua interseção são contadas duas vezes, ou seja,

{displaystyle E(S,T)=2|E(G[Scap T])|+E(Ssetminus T,T)+E(S,Tsetminus S).}

Em seguida, o lema da mistura do expansor diz que a seguinte desigualdade é válida:

{displaystyle left|E(S,T)-{frac {dcdot |S|cdot |T|}{n}}right|leq lambda {sqrt {|S|cdot |T|}}.}

Muitas propriedades dos gráficos $(n, d, λ)$ são corolários dos lemas de mistura do expansor, incluindo a seguir.

Um conjunto independente de um grafo é um subconjunto de vértices sem dois vértices adjacentes. Em um $(n, D, λ)$ -graph, um conjunto independente tem tamanho no máximo $λ n ? D$ .
O número cromático de um gráfico $G$ , $χ (G)$ , é o número mínimo de cores necessárias tal que vértices adjacentes têm cores diferentes. Hoffman mostrou que $D ? λ \leq χ (G)$ , enquanto Alon, Krivelevich e Sudakov mostraram que se $D < 2 n ? 3$ , então
${displaystyle chi (G)leq Oleft({frac {d}{log(1+d/lambda)}}right).}$
O diâmetro de um gráfico é a distância máxima entre dois vértices, onde a distância entre dois vértices é definida como o caminho mais curto entre eles. Chung mostrou que o diâmetro de um $(n, D, λ)$ - o gráfico é no máximo
${displaystyle leftlceil log {frac {n}{log(d/lambda)}}rightrceil.}$

Amostragem de caminhada do expansor

O limite de Chernoff afirma que, ao amostrar muitas amostras independentes de variáveis aleatórias no intervalo $[-1, 1]$ , com alta probabilidade a média de nossas amostras é próxima à expectativa da variável aleatória. O lema de amostragem de caminhada do expansor, devido a Ajtai, Komlós & Szemerédi (1987) e Gillman (1998), afirmam que isso também é verdadeiro ao amostrar de uma caminhada em um gráfico expansor. Isso é particularmente útil na teoria da desrandomização, uma vez que a amostragem de acordo com uma caminhada do expansor usa muito menos bits aleatórios do que a amostragem independente.

Rede de classificação AKS e halvers aproximados

As redes de classificação pegam um conjunto de entradas e executam uma série de etapas paralelas para classificar as entradas. Uma etapa paralela consiste em realizar qualquer número de comparações disjuntas e potencialmente trocar pares de entradas comparadas. A profundidade de uma rede é dada pelo número de passos paralelos que ela leva. Os gráficos do expansor desempenham um papel importante na rede de classificação AKS, que atinge a profundidade $O (log n)$ . Embora esta seja assintoticamente a profundidade mais conhecida para uma rede de classificação, a dependência de expansores torna o limite constante muito grande para uso prático.

Na rede de classificação AKS, os gráficos de expansão são usados para construir $ε$ -halvers de profundidade limitada. Um $ε$ -halver toma como entrada um comprimento $n$ permutação de $(1, \dots, n)$ e divide as entradas em dois conjuntos disjuntos $A$ e $B$ tal que para cada inteiro $k \leq n ⁄ 2$ no máximo $εk$ do $k$ as menores entradas estão em $B$ e em a maioria $εk$ do $k$ as maiores entradas estão em $A$ . Os conjuntos $A$ e $B$ são $ε$ -halving.

Seguindo Ajtai, Komlós & Szemerédi (1983), uma profundidade $d$ $ε$ -halver pode ser construído da seguinte forma. Pegue um vértice $n$ , grau $d$ expansor bipartido com partes $X$ e $Y$ de tamanho igual, de modo que cada subconjunto de vértices de tamanho no máximo $εn$ tenha pelo menos $1 - ε / ε$ vizinhos.

Os vértices do gráfico podem ser pensados como registradores que contêm entradas e as arestas podem ser consideradas como fios que comparam as entradas de dois registradores. No início, coloque arbitrariamente metade das entradas no estilo $X$ e metade das entradas no estilo $Y$ e decomponha as bordas em $d$ combinações perfeitas. O objetivo é terminar com $X$ contendo aproximadamente a metade menor das entradas e $Y$ contendo aproximadamente a metade maior das entradas. Para conseguir isso, processe sequencialmente cada correspondência comparando os registradores emparelhados pelas bordas dessa correspondência e corrija quaisquer entradas que estejam fora de ordem. Especificamente, para cada aresta da correspondência, se a entrada maior estiver no registrador em $X$ e a entrada menor estiver no registrador em $Y$ , depois troque as duas entradas para que a menor fique em $X$ e o maior está em $Y$ . É claro que este processo consiste em $d$ etapas paralelas.

Após todas as $d$ rodadas, faça $A$ para ser o conjunto de entradas nos registradores em $X$ e $B$ para ser o conjunto de entradas em registros em $Y$ para obter um $ε$ -halving. Para ver isso, observe que se um registro $u$ em $X$ e $v$ em $Y$ são conectados por uma aresta $uv$ então, após a correspondência com esta aresta ser processada, a entrada em $u$ é menor que $v$ . Além disso, esta propriedade permanece verdadeira durante todo o resto do processo. Agora, suponha que para algum $k \leq n ⁄ 2$ que mais de $εk$ das entradas $(1, \dots, k)$ estão em $B$ . Então, pelas propriedades de expansão do gráfico, os registros dessas entradas em $Y$ são conectados com pelo menos $1 - ε / ε k$ registra em estilo X. Ao todo, isso constitui mais de $k$ registros, portanto deve haver algum registro $A$ em $X$ conectado a algum registro $B$ em $Y$ de forma que a entrada final de $A$ não está em $(1, \dots, k)$ , enquanto a entrada final de $B$ é. No entanto, isso viola a propriedade anterior e, portanto, a saída define $A$ e $B$ deve ser um $ε$ -halving.

Contenido relacionado

Más resultados...