Expander (grafteori)

Expander (fra det engelske expander graph - expanding graph) er en stærkt forbundet sparsom graf , mens forbindelsesmuligheder kan bestemmes af hjørner, buer eller spektrum (se nedenfor) [1] .

Historie

Studiet af ekspandere blev indledt af Moskva-matematikerne M. S. Pinsker , L. A. Bassalygo og G. A. Margulis i halvfjerdserne af det XX århundrede. I løbet af den seneste tid har disse grafer fundet mange uventede anvendelser, for eksempel i beregningskompleksitetsteori og i kodningsteori. De viste sig også at være forbundet med dele af moderne matematik, der ligger langt fra klassisk grafteori, for eksempel med gruppeteori og talteori, og som i øjeblikket er genstand for aktiv forskning, primært udført af udenlandske matematikere. Bibliografien om dette emne omfatter hundredvis af publikationer [2] .

Definition

En ekspander er en endelig , ikke-rettet multigraf , hvor en hvilken som helst delmængde af hjørner, selvom den ikke er "for stor", er "stærkt" forbundet. Forskellige formaliseringer af disse begreber giver forskellige typer ekspandere: kantudvider , vertexudvider og spektraludvider .

En afbrudt graf er ikke en udvider. Enhver forbundet graf er en expander, men forskellige forbundet grafer har forskellige expander-parametre. Den komplette graf har de bedste ekspanderparametre, men har den højest mulige grad. Uformelt set er en graf en god expander, hvis den har en lav grad og en høj expander parameter.

Rib ekspansion

Kantforlængelsen (også isoperimetrisk tal eller Cheegers konstant ) h ( G ) af en graf G for n hjørner er defineret som

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

hvor minimum overtages alle ikke-tomme mængder S på højst n /2 toppunkter og ∂( S ) er grænsebuerne for mængden S , det vil sige buesættet med et enkelt toppunkt i S [3] .

Vertex-udvidelse

Det isoperimetriske toppunktsnummer (også vertexudvidelsen ) af en graf G er defineret som $h_{\text{out}}(G)$

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

hvor er den ydre grænse for S , det vil sige, at mængden af toppunkter fra , der har mindst én nabo i S [4] . I en variant af denne definition (kaldet den unikke nabo forlængelse ), ) erstattes af sættet af hjørner fra V med nøjagtig en nabo fra S [5] . $\partial _{\text{out}}(S)$ $V(G)\setminus S$ $\partial _{\text{out}}(S)$

Det isoperimetriske toppunkt for en graf G er defineret som $h_{\text{in}}(G)$

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

hvor er den indre grænse for S , det vil sige mængden af toppunkter af S , der har mindst én nabo i [4] . $\partial _{\text{i}}(S)$ $V(G)\setminus S$

Spektral udvidelse

Hvis G er d -regulær , er det muligt at definere i form af lineær algebra baseret på egenværdierne af tilstødende matrix A = A ( G ) af grafen G , hvor er antallet af buer mellem toppunkter i og j [ 6] . Da A er symmetrisk , har A ifølge spektralsætningen n reelle egenværdier . Det er kendt, at disse værdier ligger i intervallet [− d , d ]. $A_{{ij}}$ ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n))$

Grafen er regulær, hvis og kun hvis vektoren c for alle i = 1, …, n er en egenvektor for matricen A , og dens egenværdi er en konstant potens af grafen. Således har vi Au = du , og u er en egenvektor af matrix A med egenværdier λ 1 = d , hvor d er graden af hjørner af graf G . Det spektrale gab på grafen G er defineret som d −λ 2 og er et mål for den spektrale udvidelse af grafen G [7] . $u\in \mathbb {R} ^{n}$ $u_{i}=1$

Det er kendt, at λ n = − d , hvis og kun hvis G er todelt. I mange tilfælde, for eksempel i blandingslemmaet , er det nødvendigt nedefra at begrænse ikke kun afstanden mellem λ 1 og λ 2 , men også afstanden mellem λ 1 og den anden maksimale egenværdi i absolut værdi:

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

Fordi denne egenværdi svarer til en eller anden egenvektor ortogonal til u , kan den bestemmes ved hjælp af Rayleigh-relationen :

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

hvor

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

er den euklidiske norm for vektoren . $v\in \mathbb {R} ^{n}$

Den normaliserede version af denne definition er også meget brugt og er mere bekvem til at opnå visse resultater. I dette tilfælde betragter vi matrixen , som er overgangsmatrixen for grafen G . Alle dens egenværdier ligger mellem -1 og 1. Hvis grafen ikke er regulær, kan grafens spektrum defineres på lignende måde ved hjælp af egenværdierne af Kirchhoff-matricen . For en rettet graf bruges entalsværdierne af konjugationsmatricen A , som er lig med kvadratrødderne af egenværdierne af den symmetriske matrix A T A . ${\tfrac {1}{d}}A$

Forholdet mellem forskellige typer udvidelser

Ovenstående former for forlængelse er indbyrdes forbundne. Især for enhver d -regulær graf G ,

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

Derfor, for grafer med konstant grad, er top- og kantforlængelserne lige store.

Cheegers uligheder

I det tilfælde, hvor G er en d -regulær graf, er der en relation mellem h ( G ) og spektralgabet d − λ 2 af G . En ulighed udledt af Tanner og uafhængigt af Noga Alon og Vitali Milman [8] siger, at [9]

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

Denne ulighed er tæt forbundet med Cheeger bundet for Markov kæder, og kan opfattes som en diskret version af Cheegers ulighed i Riemann geometri .

Et lignende forhold mellem vertex isoperimetriske tal og spektralgabet er også ved at blive undersøgt [10] . Bemærk at λ 2 i artiklen svarer til 2( d − λ 2 ) her

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

Asymptotisk er tallene , og afgrænset ovenfra af det spektrale mellemrum . ${\frac {h^{2}}{d}}$ $h_{\text{out}}$ $h_{\text{i}}^{2}$ $O(d-\lambda _{2})$

Bygninger

Der er tre hovedstrategier til at skabe familier af forlængelsesgrafer [11] . Den første strategi er algebraisk og gruppeteoretisk, den anden er analytisk, ved hjælp af additiv kombinatorik , og den tredje er kombinatorisk, ved hjælp af zigzag-produktet og tilhørende kombinatoriske produkter.

Margulis - Gabber - Galil

Algebraisk konstruktion baseret på Cayley-grafer er kendt for forskellige varianter af ekspandere. Den følgende konstruktion skyldes Margulis og blev analyseret af Gabber og Galil [12] . For enhver naturlig n bygger vi en graf, G n med et sæt toppunkter , hvor . For enhver toppunkt vil dens otte naboer være ${\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ølgende sætning gælder:

Sætning. For alle n opfylder den næststørste egenværdi af grafen G n uligheden . $\lambda (G)\leq 5{\sqrt {2))$

Grev Ramanujan

Ved sætningen af Alon (Alon) og Boppana (Boppana) for alle tilstrækkeligt store d - regulære grafer, gælder uligheden , hvor λ er den anden egenværdi i absolut værdi [13] . For Ramanujan-grafer [14] . Ramanujan-grafer har således den asymptotisk mindst mulige værdi af λ og er fremragende spektrale ekspandere. $\lambda \geq 2{\sqrt {d-1}}-o(1)$ $\lambda \leq 2{\sqrt {d-1))$

Alexander Lubotsky, Philips og Sarnak (1988), Margulis (1988) og Morgenstern (1994) viste, hvordan Ramanujan-grafen eksplicit kan konstrueres [15] . Ved Friedmans sætning (Friedman, 2003) er en tilfældig d-regular graf med n toppunkter næsten en Ramanujan-graf, da

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

med sandsynlighed ved [16] . $1-o(1)$ $n\rightarrow \infty$

Applikationer og nyttige funktioner

I starten opstod interessen for ekspandere for at opbygge et stabilt netværk (telefoner eller computere) - antallet af buer af ekspansionsgrafer med en begrænset regularitetsværdi vokser lineært i forhold til antallet af toppunkter.

Udvidere er meget brugt i teorien om computere og systemer, til at konstruere algoritmer , i korrigerende koder , ekstraktorer , pseudo-tilfældige talgeneratorer , sorteringsnetværk [17] og computernetværk . De bruges også til at bevise mange vigtige resultater i beregningsmæssig kompleksitetsteori, såsom SL = L [18] og PCP-sætningen [19] . I kryptografi bruges expanders til at skabe hash-funktioner .

Nedenfor er nogle egenskaber ved expandere, der anses for nyttige på mange områder.

Blandingslemmaet

Blandingslemmaet siger , at antallet af kanter mellem S og T er omtrent lig med antallet af kanter i en tilfældig d - regulær graf. Tilnærmelse er bedre, jo mindre . I en tilfældig d - regulær graf, såvel som i en tilfældig Erdős-Rényi graf med kantvalgssandsynlighed , forventes kanter mellem S og T . $S,T\subseteq V$ ${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\))$ ${\tfrac {d}{n))$ ${\tfrac {d}{n}}\cdot |S|\cdot |T|$

Mere formelt, lad E ( S , T ) angive antallet af kanter mellem S og T. Hvis disse to sæt skærer hinanden, tælles buerne i skæringspunktet to gange, således at

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

Blandingslemmaet siger, at [20]

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

hvor λ er den absolutte værdi af den normaliserede næststørste egenværdi.

Bilu og Linial har for nylig vist, at det omvendte også er sandt, det vil sige, givet uligheden i lemmaet, er den næststørste egenværdi [21] . $O(d\lambda \cdot (1+\log(1/\lambda )))$

Expander Wanderings

Ifølge Chernoff-grænsen , hvis vi vælger mange uafhængige tilfældige værdier fra intervallet [−1, 1], med en høj grad af sandsynlighed, vil gennemsnittet af de valgte værdier være tæt på den matematiske forventning af tilfældigheden variabel. Expander-walk-lemmaet siger ifølge Ajtari, Komlosh og Szemeredy [22] og Gilman [23] , at det samme gælder for expander-vandringer. Dette er nyttigt i derandomiseringsteori , da expander-walken bruger mange færre tilfældige bits end en tilfældig uafhængig prøve.

Se også

Noter

↑ AMS, 2006 .
↑ Gashkov, 2009 .
↑ AMS, 2006 , Definition 2.1.
↑ 12 Bobkov, 2000 .
↑ AlonCapalbo, 2002 .
↑ AMS, 2006 , afsnit 2.3.
↑ AMS, 2006 Spectral gap definition taget fra afsnit 2.3.
↑ AlonSpencer, 2011 .
↑ AMS, 2006 , Sætning 2.4.
↑ Bobkov, 2000 , Sætning 1 på s. 156.
↑ Yehudayoff, 2012 .
↑ Goldreich, 2011 , se fx s. 9.
↑ AMS, 2006 , Sætning 2.7.
↑ AMS, 2006 , Definition 5.11.
↑ AMS, 2006 , sætning 5.12.
↑ AMS, 2006 , sætning 7.10.
↑ ACM, 1983 .
↑ Reingold, 2008 .
↑ Dinur, 2007 .
↑ Forklaring af blandingslemmaet. [en]
↑ Omvendt udsagn til blandingslemmaet. [2]
↑ ACM, 1987 .
↑ Gillman, 1998 .

Litteratur

Bøger

SB Gashkov, Expander grafer og deres anvendelser i kodningsteori. — M .: MTsNMO , 2009. — S. 70–122. — (Matematisk uddannelse, tredje serie).

Noga Alon, Joel Spencer. Den probabilistiske metode. — 3. — 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, gruppeteori og Ramanujan-grafer. - Cambridge University Press , 2003. - V. 55. - ISBN 0-521-53143-8 .
Mike Krebs, Anthony. Expander-familier og Cayley-grafer: En begyndervejledning. - Oxford University Press , 2011. - ISBN 0-19-976711-4 .

Forskningsartikler

Alon, N.; Capalbo, M. Eksplicitte, unikke naboer // The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings .. - 2002. - S. 73 .

Shlomo Hoory, Nathan Linial, Avi Widgerson. Expander grafer og deres anvendelser // Bulletin (ny serie) fra American Mathematical Society. - 2006. - T. 43 , no. 4 . — S. 439–561 . - doi : 10.1090/S0273-0979-06-01126-8 .
Bobkov S., Houdré C., Tetali P. λ ∞ , vertex isoperimetri og koncentration // Combinatorica. - 2000. - T. 20 , no. 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-sætningen ved gap amplification // Journal of the ACM. - 2007. - T. 54 , no. 3 . - S. 12 . - doi : 10.1145/1236457.1236459 . .
D. Gillman. A Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. - Selskab for Industriel og Anvendt Matematik, 1998. - V. 27 , Nr. 4 ,. - S. 1203-1220 . - doi : 10.1137/S0097539794268765 .
Oded Goldreich. Grundlæggende fakta om Expander Graphs // Studier i kompleksitet og kryptografi. - 2011. - S. 451-464 . - doi : 10.1007/978-3-642-22670-0_30 .
Omer Reingold. Udirigeret forbindelse i log-space // Journal of the ACM . - 2008. - T. 55 , no. 4 . - doi : 10.1145/1391289.1391291 .
Yehudayoff, Amir. Beviser ekspansion i tre trin. - 2012. - T. 43 , no. 3 . — s. 67–84 . - doi : 10.1145/2421096.2421115 .