Expander (teoria grafurilor)

Expander (din limba engleză expander graph - expanding graph) este un graf rar conectat puternic , în timp ce conectivitatea poate fi determinată de vârfuri, arce sau spectru (vezi mai jos) [1] .

Istorie

Studiul expansoarelor a fost inițiat de matematicienii moscoviți M. S. Pinsker , L. A. Bassalygo și G. A. Margulis în anii șaptezeci ai secolului XX. De-a lungul timpului, aceste grafice au găsit multe aplicații neașteptate, de exemplu, în teoria complexității computaționale și în teoria codificării. De asemenea, s-au dovedit a fi conectate cu secțiuni ale matematicii moderne care sunt departe de teoria clasică a grafurilor, de exemplu, cu teoria grupurilor și teoria numerelor, și sunt în prezent subiectul unor cercetări active, conduse în principal de matematicieni străini. Bibliografia pe această temă cuprinde sute de publicații [2] .

Definiție

Un expander este un multigraf finit nedirecționat în care orice subset de vârfuri, deși nu este „prea mare”, este „puternic” conectat. Diferite formalizări ale acestor concepte dau diferite tipuri de expansoare: expansor de margine , expansor de vârf și expandor spectral .

Un grafic deconectat nu este un expandator. Orice graf conectat este un expander, dar diferite grafuri conectate au diferiți parametri de expander. Graficul complet are cei mai buni parametri de expandare, dar are cel mai mare grad posibil. Informal vorbind, un grafic este un bun expander dacă are un grad scăzut și un parametru de expander ridicat.

Extindere nervură

Extensia muchiei (de asemenea, numărul izoperimetric sau constanta lui Cheeger ) h ( G ) a unui grafic G pentru n vârfuri este definită ca

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

unde minimul este preluat peste toate multimile nevide S de cel mult n /2 varfuri si ∂( S ) sunt arcele de limita ale multimii S , adica multimea arcelor cu un singur varf in S [3] .

Extensie de vârf

Numărul izoperimetric al vârfurilor (de asemenea, extensia vârfurilor ) al unui grafic G este definit ca $h_{\text{out}}(G)$

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

unde este granița exterioară a lui S , adică mulțimea vârfurilor din care au cel puțin un vecin în S [4] . Într-o variantă a acestei definiții (numită extensia vecină unică ), ) este înlocuită cu mulțimea de vârfuri din V cu exact un vecin din S [5] . $\partial _{\text{out}}(S)$ $V(G)\setminus S$ $\partial _{\text{out}}(S)$

Numărul izoperimetric de vârf al unui grafic G este definit ca $h_{\text{in}}(G)$

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

unde este granița interioară a lui S , adică mulțimea vârfurilor lui S care au cel puțin un vecin în [4] . $\partial _{\text{in}}(S)$ $V(G)\setminus S$

Expansiunea spectrală

Dacă G este d - regular , este posibil să se definească în termeni de algebră liniară pe baza valorilor proprii ale matricei de adiacență A = A ( G ) a graficului G , unde este numărul de arce dintre vârfurile i și j [ 6] . Deoarece A este simetric , conform teoremei spectrale , A are n valori proprii reale . Se știe că aceste valori se află în intervalul [− d , d ]. $A_{{ij}}$ $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n)$

Graficul este regulat dacă și numai dacă vectorul c pentru tot i = 1, …, n este un vector propriu al matricei A , iar valoarea sa proprie este o putere constantă a graficului. Astfel, avem Au = du , iar u este un vector propriu al matricei A cu valori proprii λ 1 = d , unde d este gradul vârfurilor graficului G . Intervalul spectral al graficului G este definit ca d −λ 2 și este o măsură a expansiunii spectrale a graficului G [7] . $u\in \mathbb {R} ^{n}$ $u_{i}=1$

Se știe că λ n = − d dacă și numai dacă G este bipartit. În multe cazuri, de exemplu, în lema de amestecare , este necesar să se limiteze de jos nu numai decalajul dintre λ 1 și λ 2 , ci și decalajul dintre λ 1 și a doua valoare proprie maximă în valoare absolută:

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

Deoarece această valoare proprie corespunde unui vector propriu ortogonal cu u , ea poate fi determinată folosind relația Rayleigh :

\lambda =\max _{0\neq v\perp u}{\frac {\|Av\|_{2)}{\|v\|_{2))},

Unde

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

este norma euclidiană a vectorului . $v\in \mathbb {R} ^{n}$

Versiunea normalizată a acestei definiții este, de asemenea, utilizată pe scară largă și este mai convenabilă pentru obținerea anumitor rezultate. În acest caz, considerăm matricea , care este matricea de tranziție a graficului G . Toate valorile sale proprii se află între -1 și 1. Dacă graficul nu este regulat, spectrul graficului poate fi definit într-un mod similar folosind valorile proprii ale matricei Kirchhoff . Pentru un grafic direcționat, se folosesc valorile singulare ale matricei de conjugare A , care sunt egale cu rădăcinile pătrate ale valorilor proprii ale matricei simetrice A T A. ${\tfrac {1}{d}}A$

Relația dintre diferitele tipuri de extensie

Tipurile de extensie de mai sus sunt interdependente. În special, pentru orice graf d -regular G ,

h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).

Prin urmare, pentru graficele de grad constant, extensiile vârfurilor și marginilor sunt egale ca mărime.

Inegalitățile lui Cheeger

În cazul în care G este un graf d - regular, există o relație între h ( G ) și decalajul spectral d − λ 2 al lui G . O inegalitate derivată de Tanner și independent de Noga Alon și Vitali Milman [8] afirmă că [9]

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

Această inegalitate este strâns legată de limita Cheeger pentru lanțurile Markov și poate fi considerată ca o versiune discretă a inegalității lui Cheeger în geometria Riemann .

O relație similară între numerele izoperimetrice a vârfurilor și decalajul spectral este de asemenea studiată [10] . Rețineți că λ 2 din articol corespunde aici cu 2( d − λ 2 ).

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

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

Asimptotic , numerele și sunt mărginite de sus de decalajul spectral . ${\frac {h^{2}}{d}}$ $h_{\text{out}}$ $h_{\text{in}}^{2}$ $O(d-\lambda _{2})$

Clădiri

Există trei strategii principale pentru crearea familiilor de grafice de extensie [11] . Prima strategie este algebrică și teoretică de grup, a doua este analitică, folosind combinatorie aditivă , iar a treia este combinatorică, folosind produsul în zig-zag și produsele combinatorii asociate.

Margulis - Gabber - Galil

Construcția algebrică bazată pe graficele Cayley este cunoscută pentru diferite variante de expandoare. Următoarea construcție se datorează lui Margulis și a fost analizată de Gabber și Galil [12] . Pentru orice n natural construim un grafic, G n cu un set de vârfuri , unde . Pentru orice vârf , cei opt vecini ai săi vor fi $\mathbb {Z} _{n}\times \mathbb {Z} _{n)$ $\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z}$ $(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n)$

(x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).

Următoarea teoremă este valabilă:

Teorema. Pentru tot n , a doua cea mai mare valoare proprie a graficului G n satisface inegalitatea . $\lambda (G)\leq 5{\sqrt {2)}$

Contele Ramanujan

Prin teorema lui Alon (Alon) și Boppana (Boppana) pentru toate graficele d -regulate suficient de mari, inegalitatea este valabilă , unde λ este a doua valoare proprie în valoare absolută [13] . Pentru graficele Ramanujan [14] . Astfel, graficele Ramanujan au cea mai mică valoare asimptotic posibilă a lui λ și sunt excelente expansoare spectrale. $\lambda \geq 2{\sqrt {d-1}} -o(1)$ $\lambda \leq 2{\sqrt {d-1)}$

Alexander Lubotsky, Philips și Sarnak (1988), Margulis (1988) și Morgenstern (1994) au arătat cum poate fi construit în mod explicit graficul Ramanujan [15] . După teorema lui Friedman (Friedman, 2003), un graf d-regular aleatoriu cu n vârfuri este aproape un graf Ramanujan, deoarece

\lambda \leq 2{\sqrt {d-1}}+\epsilon

cu probabilitate la [16] . $1-o(1)$ $n\rightarrow \infty$

Aplicații și caracteristici utile

Inițial, interesul pentru expandoare a apărut pentru a construi o rețea stabilă (telefoane sau computere) - numărul de arce de grafice de expansiune cu o valoare limitată de regularitate crește liniar în raport cu numărul de vârfuri.

Expansoarele sunt utilizate pe scară largă în teoria calculatoarelor și sistemelor, pentru construirea de algoritmi , în coduri corective , extractoare , generatoare de numere pseudoaleatoare , rețele de sortare [17] și rețele de calculatoare . Ele sunt, de asemenea, utilizate pentru a demonstra multe rezultate importante în teoria complexității computaționale, cum ar fi SL = L [18] și Teorema PCP [19] . În criptografie , expansoarele sunt folosite pentru a crea funcții hash .

Mai jos sunt câteva proprietăți ale expansoarelor care sunt considerate utile în multe domenii.

Lema de amestecare

Lema de amestecare afirmă că pentru oricare două submulțimi de vârfuri , numărul de muchii dintre S și T este aproximativ egal cu numărul de muchii dintr-un grafic aleator d - regulat. Aproximarea este mai bună, cu atât mai mică . Într-un grafic aleator d - regular, precum și într-un grafic aleatoriu Erdős-Rényi cu probabilitate de selecție a muchiei , sunt așteptate muchii între S și T. $S,T\subseteq V$ ${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\))$ ${\tfrac {d}{n)}$ ${\tfrac {d}{n}}\cdot |S|\cdot |T|$

Mai formal, fie E ( S , T ) să desemneze numărul de muchii dintre S și T . Dacă aceste două mulțimi se intersectează, arcele de la intersecție sunt numărate de două ori, astfel încât

E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)

Lema de amestecare afirmă că [20]

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

unde λ este valoarea absolută a celei de-a doua valori proprii ca mărime normalizate .

Bilu și Linial au arătat recent că și invers este adevărat, adică având în vedere inegalitatea din lemă, a doua cea mai mare valoare proprie este [21] . $O(d\lambda \cdot (1+\log(1/\lambda )))$

Expander Wanderings

Conform limitei Chernoff , dacă alegem multe valori aleatoare independente din intervalul [−1, 1], cu un grad ridicat de probabilitate, media valorilor selectate va fi apropiată de așteptarea matematică a aleatoriei variabil. Lema expansoare de mers, conform lui Ajtari, Komlosh și Szemeredy [22] și Gilman [23] , afirmă că același lucru este valabil și pentru plimbările expander. Acest lucru este util în teoria derandomizării , deoarece mersul expander folosește mult mai puțini biți aleatori decât un eșantion independent aleatoriu.

Vezi și

Note

↑ AMS, 2006 .
↑ Gashkov, 2009 .
↑ AMS, 2006 , Definiția 2.1.
↑ 12 Bobkov, 2000 .
↑ AlonCapalbo, 2002 .
↑ AMS, 2006 , secțiunea 2.3.
↑ AMS, 2006 Definiția decalajului spectral preluată din secțiunea 2.3.
↑ AlonSpencer, 2011 .
↑ AMS, 2006 , Teorema 2.4.
↑ Bobkov, 2000 , Teorema 1 la p. 156.
↑ Yehudayoff, 2012 .
↑ Goldreich, 2011 , vezi, de exemplu, p. 9.
↑ AMS, 2006 , Teorema 2.7.
↑ AMS, 2006 , Definiția 5.11.
↑ AMS, 2006 , Teorema 5.12.
↑ AMS, 2006 , Teorema 7.10.
↑ ACM, 1983 .
↑ Reingold, 2008 .
↑ Dinur, 2007 .
↑ Explicația lemei de amestecare. [unu]
↑ Inversați afirmația cu lema de amestecare. [2]
↑ ACM, 1987 .
↑ Gillman, 1998 .

Literatură

Cărți

SB Gashkov, Graficele expansoare și aplicațiile lor în teoria codificării. — M .: MTsNMO , 2009. — S. 70–122. — (Educația matematică, seria a treia).

Noga Alon, Joel Spencer. Metoda probabilistică. — al 3-lea. — John Wiley & Sons , 2011.
Chung, Fan R. K. Teoria graficelor spectrale. - Societatea Americană de Matematică , 1997. - V. 92. - (Seria de conferințe regionale CBMS în matematică). — ISBN 0-8218-0315-8 .
Guiliana Davidoff, Peter Sarnak, Alain Valette. Teoria elementară a numerelor, teoria grupurilor și graficele Ramanujan. - Cambridge University Press , 2003. - V. 55. - ISBN 0-521-53143-8 .
Mike Krebs, Anthony. Familii de expansiune și grafice Cayley: un ghid pentru începători. - Oxford University Press , 2011. - ISBN 0-19-976711-4 .

Articole de cercetare

Alon, N.; Capalbo, M. Explicit unic-neighbor expanders // Al 43-lea Simpozion anual IEEE privind fundamentele informaticii, 2002. Proceedings .. - 2002. - P. 73 .

Shlomo Hoory, Nathan Linial, Avi Widgerson. Grafice de expansiune și aplicațiile acestora // Buletin (serie nouă) al Societății Americane de Matematică. - 2006. - T. 43 , nr. 4 . — S. 439–561 . - doi : 10.1090/S0273-0979-06-01126-8 .
Bobkov S., Houdré C., Tetali P. λ ∞ , izoperimetrie și concentrație a vârfurilor // Combinatorica. - 2000. - T. 20 , nr. 2 . — S. 153–172 . - doi : 10.1007/s004930070018 . .

Miklós Ajtai, János Komlós, Endre Szemerédi. Proceedings of the 15th Annual ACM Symposium on Theory of Computing . - 1983. - S. 1-9 . - ISBN 0-89791-099-0 . - doi : 10.1145/800061.808726 .
M. Ajtai,J. Komlos, E. Szemeridi. Proceedings of the 19th Annual ACM Symposium on Theory of Computing // ACM. - 1987. - S. 132-140 . — ISBN 0-89791-221-7 . - doi : 10.1145/28395.28410 .
Irit Dinur. Teorema PCP prin amplificarea decalajului // Journal of the ACM. - 2007. - T. 54 , nr. 3 . - S. 12 . - doi : 10.1145/1236457.1236459 . .
D. Gillman. A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. - Societatea de Matematică Industrială și Aplicată, 1998. - V. 27 , nr. 4, . - S. 1203-1220 . - doi : 10.1137/S0097539794268765 .
Oded Goldreich. Date de bază despre graficele expansoare // Studii în complexitate și criptografie. - 2011. - S. 451-464 . - doi : 10.1007/978-3-642-22670-0_30 .
Omer Reingold. Conectivitate nedirecționată în spațiul de jurnal // Jurnalul ACM . - 2008. - T. 55 , nr. 4 . - doi : 10.1145/1391289.1391291 .
Yehudayoff, Amir. Demonstrarea extinderii în trei etape. - 2012. - T. 43 , nr. 3 . — p. 67–84 . - doi : 10.1145/2421096.2421115 .