Expander (grafteori)

Expander (från engelska expander graph- expanding graph) är en starkt sammankopplad sparsam graf , medan konnektivitet kan bestämmas av hörn, bågar eller spektrum (se nedan) [1] .

Historik

Studiet av expanderare initierades av Moskva-matematikerna M. S. Pinsker , L. A. Bassalygo och G. A. Margulis på sjuttiotalet av XX-talet. Under den senaste tiden har dessa grafer hittat många oväntade tillämpningar, till exempel i beräkningskomplexitetsteori och i kodningsteori. De visade sig också hänga samman med delar av modern matematik som är långt ifrån klassisk grafteori, till exempel med gruppteori och talteori, och som för närvarande är föremål för aktiv forskning, främst bedriven av utländska matematiker. Bibliografin om detta ämne innehåller hundratals publikationer [2] .

Definition

En expander är en ändlig oriktad multigraf där varje delmängd av hörn, även om den inte är "för stor", är "starkt" sammankopplad. Olika formaliseringar av dessa begrepp ger olika typer av expanderare: kantexpanderare , vertexexpanderare och spektralexpanderare .

En frånkopplad graf är inte en expanderare. Varje ansluten graf är en expander, men olika anslutna grafer har olika expanderparametrar. Hela grafen har de bästa expanderparametrarna, men har högsta möjliga grad. Informellt sett är en graf en bra expanderare om den har en låg grad och en hög expanderparameter.

Ribbexpansion

Kantförlängningen (även isoperimetriskt tal eller Cheegers konstant ) h ( G ) av en graf G för n hörn definieras som

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

där minimum tas över alla icke-tomma mängder S med högst n /2 hörn och ∂( S ) är gränsbågarna för mängden S , det vill säga mängden bågar med en enda vertex i S [3] .

Vertex extension

Det isoperimetriska vertextalet (även vertexförlängning ) för en graf G definieras som $h_{\text{out}}(G)$

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

var är den yttre gränsen för S , det vill säga mängden hörn från som har minst en granne i S [4] . I en variant av denna definition (kallad den unika granneförlängningen ), ) ersätts av uppsättningen av hörn från V med exakt en granne från S [5] . $\partial _{\text{out}}(S)$ $V(G)\setminus S$ $\partial _{\text{out}}(S)$

Det isoperimetriska vertextalet för en graf G definieras som $h_{\text{in}}(G)$

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

var är den inre gränsen för S , det vill säga mängden hörn av S som har minst en granne i [4] . $\partial _{\text{i}}(S)$ $V(G)\setminus S$

Spektral expansion

Om G är d -reguljär är det möjligt att definiera i termer av linjär algebra baserat på egenvärdena för närliggande matris A = A ( G ) i grafen G , där är antalet bågar mellan hörn i och j [ 6] . Eftersom A är symmetrisk , enligt spektralsatsen , har A n reella egenvärden . Det är känt att dessa värden ligger i intervallet [− d , d ]. $A_{{ij}}$ ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n))$

Grafen är regelbunden om och endast om vektorn c för alla i = 1, …, n är en egenvektor för matrisen A , och dess egenvärde är en konstant potens av grafen. Således har vi Au = du , och u är en egenvektor för matris A med egenvärden λ 1 = d , där d är graden av hörn i grafen G . Spektralgapet i grafen G definieras som d −λ 2 och är ett mått på den spektrala expansionen av grafen G [7] . $u\in \mathbb {R} ^{n}$ $u_{i}=1$

Det är känt att λ n = − d om och endast om G är tvådelad. I många fall, till exempel, i blandningslemma , är det nödvändigt att underifrån begränsa inte bara gapet mellan λ 1 och λ 2 , utan även gapet mellan λ 1 och det andra maximala egenvärdet i absolut värde:

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

Eftersom detta egenvärde motsvarar någon egenvektor som är ortogonal mot u , kan det bestämmas med hjälp av Rayleigh-relationen :

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

var

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

är den euklidiska normen för vektorn . $v\in \mathbb {R} ^{n}$

Den normaliserade versionen av denna definition används också i stor utsträckning och är bekvämare för att få vissa resultat. I det här fallet betraktar vi matrisen , som är övergångsmatrisen för grafen G . Alla dess egenvärden ligger mellan −1 och 1. Om grafen inte är regelbunden kan grafens spektrum definieras på liknande sätt med hjälp av Kirchhoff-matrisens egenvärden . För en riktad graf används singularvärdena för konjugationsmatrisen A , som är lika med kvadratrötterna av egenvärdena för den symmetriska matrisen A T A . ${\tfrac {1}{d}}A$

Samband mellan olika typer av tillägg

Ovanstående typer av förlängning är relaterade till varandra. Speciellt för varje d -reguljär graf G ,

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

Därför, för grafer med konstant grad, är vertex- och kantförlängningarna lika stora.

Cheegers ojämlikheter

I fallet när G är en d -reguljär graf, finns det ett samband mellan h ( G ) och spektralgapet d − λ 2 för G . En ojämlikhet härledd av Tanner och oberoende av Noga Alon och Vitali Milman [8] säger att [9]

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

Denna ojämlikhet är nära besläktad med Cheeger bunden för Markov-kedjor, och kan ses som en diskret version av Cheegers ojämlikhet i Riemann geometri .

Ett liknande förhållande mellan vertex isoperimetriska tal och spektralgapet studeras också [10] . Observera att λ 2 i artikeln motsvarar 2( d − λ 2 ) här

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})))

Asymptotiskt begränsas siffrorna och ovanifrån av det spektrala gapet . ${\frac {h^{2}}{d}}$ $h_{\text{out}}$ $h_{\text{i}}^{2}$ $O(d-\lambda _{2})$

Byggnader

Det finns tre huvudstrategier för att skapa familjer av förlängningsdiagram [11] . Den första strategin är algebraisk och gruppteoretisk, den andra är analytisk, med additiv kombinatorik , och den tredje är kombinatorisk, med hjälp av sicksackprodukten och associerade kombinatoriska produkter.

Margulis - Gabber - Galil

Algebraisk konstruktion baserad på Cayley-grafer är känd för olika varianter av expanders. Följande konstruktion beror på Margulis och analyserades av Gabber och Galil [12] . För alla naturliga n bygger vi en graf, G n med en uppsättning hörn , där . För varje vertex kommer dess åtta grannar att vara ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n))$ $\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z}$ ${\displaystyle (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)).

Följande teorem gäller:

Sats. För alla n uppfyller det näst största egenvärdet i grafen G n olikheten . $\lambda (G)\leq 5{\sqrt {2))$

Greve Ramanujan

Genom satsen Alon (Alon) och Boppana (Boppana) för alla tillräckligt stora d -reguljära grafer gäller olikheten , där λ är det andra egenvärdet i absolutvärde [13] . För Ramanujan-grafer [14] . Således har Ramanujan-grafer det asymptotiskt minsta möjliga värdet av λ och är utmärkta spektralexpanderare. $\lambda \geq 2{\sqrt {d-1}}-o(1)$ $\lambda \leq 2{\sqrt {d-1))$

Alexander Lubotsky, Philips och Sarnak (1988), Margulis (1988) och Morgenstern (1994) visade hur Ramanujan-grafen explicit kan konstrueras [15] . Enligt Friedmans teorem (Friedman, 2003) är en slumpmässig d-regular graf med n hörn nästan en Ramanujan-graf, eftersom

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

med sannolikhet vid [16] . $1-o(1)$ $n\rightarrow \infty$

Applikationer och användbara funktioner

Inledningsvis uppstod intresse för expanderare för att bygga ett stabilt nätverk (telefoner eller datorer) - antalet bågar av expansionsgrafer med ett begränsat regularitetsvärde växer linjärt med avseende på antalet hörn.

Expanderare används i stor utsträckning i teorin om datorer och system, för att konstruera algoritmer , i korrigeringskoder , extraherare , pseudoslumptalsgeneratorer , sorteringsnätverk [17] och datornätverk . De används också för att bevisa många viktiga resultat i beräkningskomplexitetsteori som SL = L [18] och PCP-teorem [19] . I kryptografi används expanders för att skapa hashfunktioner .

Nedan finns några egenskaper hos expanders som anses användbara inom många områden.

Blandningslemmat

Blandningslemmat anger att för två delmängder av hörn är antalet kanter mellan S och T ungefär lika med antalet kanter i en slumpmässig d - reguljär graf. Approximation är bättre, ju mindre . I en slumpmässig d -reguljär graf, såväl som i en slumpmässig Erdős-Rényi-graf med kantvalsannolikhet , förväntas kanter mellan S och T . $S,T\subseteq V$ ${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\))$ ${\tfrac {d}{n))$ ${\tfrac {d}{n}}\cdot |S|\cdot |T|$

Mer formellt, låt E ( S , T ) beteckna antalet kanter mellan S och T . Om dessa två uppsättningar skär varandra, räknas bågarna vid skärningspunkten två gånger, så att

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

Blandningslemmat säger att [20]

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

där λ är det absoluta värdet av det normaliserade näst största egenvärdet.

Bilu och Linial har nyligen visat att det omvända också är sant, det vill säga med tanke på olikheten i lemma är det näst största egenvärdet [21] . $O(d\lambda \cdot (1+\log(1/\lambda )))$

Expander Wanderings

Enligt Chernoff-gränsen , om vi väljer många oberoende slumpmässiga värden från intervallet [−1, 1], med en hög grad av sannolikhet, kommer medelvärdet av de valda värdena att vara nära den matematiska förväntan av slumpen variabel. Expanderpromenadslemmat, enligt Ajtari, Komlosh och Szemeredy [22] och Gilman [23] , anger att samma sak gäller för expanderpromenader. Detta är användbart i derandomiseringsteori , eftersom expanderpromenaden använder många färre slumpmässiga bitar än ett slumpmässigt oberoende urval.

Se även

Anteckningar

↑ AMS, 2006 .
↑ Gashkov, 2009 .
↑ AMS, 2006 , Definition 2.1.
↑ 12 Bobkov, 2000 .
↑ AlonCapalbo, 2002 .
↑ AMS, 2006 , avsnitt 2.3.
↑ AMS, 2006 Spektralgapdefinition hämtad från avsnitt 2.3.
↑ AlonSpencer, 2011 .
↑ AMS, 2006 , sats 2.4.
↑ Bobkov, 2000 , Sats 1 på s. 156.
↑ Yehudayoff, 2012 .
↑ Goldreich, 2011 , se t.ex. s. 9.
↑ AMS, 2006 , sats 2.7.
↑ AMS, 2006 , Definition 5.11.
↑ AMS, 2006 , sats 5.12.
↑ AMS, 2006 , sats 7.10.
↑ ACM, 1983 .
↑ Reingold, 2008 .
↑ Dinur, 2007 .
↑ Förklaring av blandningslemma. [ett]
↑ Omvänd uttalande till blandningslemma. [2]
↑ ACM, 1987 .
↑ Gillman, 1998 .

Litteratur

Böcker

SB Gashkov, Expandergrafer och deras tillämpningar i kodningsteori. — M .: MTsNMO , 2009. — S. 70–122. — (Matematisk utbildning, tredje serien).

Noga Alon, Joel Spencer. Den probabilistiska metoden. — 3:a. — John Wiley & Sons , 2011.
Chung, Fan R. K. Spectral Graph Theory. - American Mathematical Society , 1997. - V. 92. - (CBMS Regional Conference Series in Mathematics). — ISBN 0-8218-0315-8 .
Guiliana Davidoff, Peter Sarnak, Alain Valette. Elementär talteori, gruppteori och Ramanujan-grafer. - Cambridge University Press , 2003. - V. 55. - ISBN 0-521-53143-8 .
Mike Krebs, Anthony. Expanderfamiljer och Cayley-grafer: En nybörjarguide. - Oxford University Press , 2011. - ISBN 0-19-976711-4 .

Forskningsartiklar

Alon, N.; Capalbo, M. Explicit unika granneexpanderar // The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings .. - 2002. - P. 73 .

Shlomo Hoory, Nathan Linial, Avi Widgerson. Expandergrafer och deras tillämpningar // Bulletin (ny serie) från American Mathematical Society. - 2006. - T. 43 , nr. 4 . — S. 439–561 . - doi : 10.1090/S0273-0979-06-01126-8 .
Bobkov S., Houdré C., Tetali P. λ ∞ , vertex isoperimetri och koncentration // Combinatorica. - 2000. - T. 20 , nej. 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. Szemeredi. 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. PCP-satsen genom gapförstärkning // 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. - Society for Industrial and Applied Mathematics, 1998. - V. 27 , nr. 4, . - S. 1203-1220 . - doi : 10.1137/S0097539794268765 .
Oded Goldreich. Grundläggande fakta om Expander Graphs // Studier i komplexitet och kryptografi. - 2011. - S. 451-464 . - doi : 10.1007/978-3-642-22670-0_30 .
Omer Reingold. Oriktad anslutning i loggutrymme // Journal of the ACM . - 2008. - T. 55 , nr. 4 . - doi : 10.1145/1391289.1391291 .
Yehudayoff, Amir. Bevisar expansion i tre steg. - 2012. - T. 43 , nr. 3 . — s. 67–84 . - doi : 10.1145/2421096.2421115 .