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] .
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] .
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.
Extensia muchiei (de asemenea, numărul izoperimetric sau constanta lui Cheeger ) h ( G ) a unui grafic G pentru n vârfuri este definită ca
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] .
Numărul izoperimetric al vârfurilor (de asemenea, extensia vârfurilor ) al unui grafic G este definit ca
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] .
Numărul izoperimetric de vârf al unui grafic G este definit ca
unde este granița interioară a lui S , adică mulțimea vârfurilor lui S care au cel puțin un vecin în [4] .
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 ].
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] .
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ă:
.Deoarece această valoare proprie corespunde unui vector propriu ortogonal cu u , ea poate fi determinată folosind relația Rayleigh :
Unde
este norma euclidiană a vectorului .
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.
Tipurile de extensie de mai sus sunt interdependente. În special, pentru orice graf d -regular G ,
Prin urmare, pentru graficele de grad constant, extensiile vârfurilor și marginilor sunt egale ca mărime.
Î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]
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 ).
Asimptotic , numerele și sunt mărginite de sus de decalajul spectral .
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.
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
Următoarea teoremă este valabilă:
Teorema. Pentru tot n , a doua cea mai mare valoare proprie a graficului G n satisface inegalitatea .
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.
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
cu probabilitate la [16] .
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 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.
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
.Lema de amestecare afirmă că [20]
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] .
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.
Cărți
Articole de cercetare