Expander (gráfelmélet)

Az Expander (az angol expander gráfból - expanding graph) egy erősen összefüggő ritka gráf , míg a konnektivitást csúcsok, ívek vagy spektrum határozzák meg (lásd alább) [1] .

Történelem

Az expanderek tanulmányozását M. S. Pinsker , L. A. Bassalygo és G. A. Margulis moszkvai matematikusok kezdeményezték a XX. század hetvenes éveiben. Az elmúlt idők során ezek a grafikonok sok váratlan alkalmazásra találtak, például a számítási komplexitás-elméletben és a kódoláselméletben. Kiderült, hogy a modern matematika olyan szakaszaihoz is kapcsolódnak, amelyek távol állnak a klasszikus gráfelmélettől, például a csoportelmélettel és a számelmélettel, és jelenleg is aktív kutatás tárgyát képezik, főleg külföldi matematikusok. A témával kapcsolatos bibliográfia több száz publikációt tartalmaz [2] .

Definíció

Az expander egy véges, irányítatlan multigráf , amelyben a csúcsok bármely részhalmaza, bár nem túl nagy, "erősen" kapcsolódik. E fogalmak különféle formalizálásai különböző típusú bővítőket adnak: élbővítőt , csúcsbővítőt és spektrális bővítőt .

A szétkapcsolt gráf nem bővítő. Bármely összekapcsolt gráf bővítő, de a különböző összekapcsolt gráfoknak eltérő bővítőparaméterei vannak. A teljes gráf a legjobb bővítő paraméterekkel rendelkezik, de a lehető legmagasabb foka van. Informálisan szólva egy gráf akkor jó bővítő, ha alacsony foka és magas bővítőparamétere van.

Bordatágítás

Egy G gráf élkiterjesztése (szintén izoperimetrikus szám vagy Cheeger -állandó ) h ( G ) n csúcsra a következőképpen van definiálva:

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

ahol a minimum átveszi az összes legfeljebb n /2 csúcsú nem üres S halmazt, és ∂( S ) az S halmaz határívei, vagyis az S -beli egyetlen csúcsú ívek halmaza [3] .

Vertex kiterjesztése

A G gráf csúcs izoperimetrikus száma (szintén csúcskiterjesztés ) a következőképpen van definiálva $h_{\text{out}}(G)$

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

ahol S külső határa , vagyis azon csúcsok halmaza, amelyeknek S -ben legalább egy szomszédja van [4] . Ennek a definíciónak egy változatában (amelyet egyedi szomszéd kiterjesztésnek neveznek) ) a V - ből származó csúcsok halmaza helyettesíti pontosan egy S -ből származó szomszéddal [5] . $\partial _{\text{out}}(S)$ $V(G)\setminus S$ $\partial _{\text{out}}(S)$

A G gráf csúcs izoperimetrikus számát a következőképpen definiáljuk $h_{\text{in}}(G)$

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

ahol S belső határa , vagyis S azon csúcsainak halmaza , amelyeknek legalább egy szomszédja van a [4]-ben . $\partial _{\text{in}}(S)$ $V(G)\setminus S$

Spektrális expanzió

Ha G d - reguláris , akkor a G gráf A = A ( G ) szomszédsági mátrixának sajátértékei alapján lineáris algebra segítségével definiálható , ahol az i és j csúcsok közötti ívek száma [ 6] . Mivel A szimmetrikus , a spektrális tétel szerint A -nak n valós sajátértéke van . Ismeretes, hogy ezek az értékek a [− d , d ] intervallumban vannak. $A_{{ij}}$ ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n))$

A gráf akkor és csak akkor szabályos, ha a c vektor minden i = 1, …, n esetén az A mátrix sajátvektora, sajátértéke pedig a gráf állandó hatványa. Így van Au = du , és u az A mátrix egy sajátvektora λ 1 = d sajátértékekkel , ahol d a G gráf csúcsainak foka . A G gráf spektrális rése d −λ 2 - ként van definiálva, és a G gráf spektrális bővülésének mértéke [7] . $u\in \mathbb {R} ^{n}$ $u_{i}=1$

Ismeretes, hogy λ n = − d akkor és csak akkor, ha G kétrészes. Sok esetben, például a keverési lemmában , nem csak a λ 1 és λ 2 közötti rést kell alulról korlátozni , hanem a λ 1 és a második maximális sajátérték közötti rést is abszolút értékben:

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

Mivel ez a sajátérték valamilyen u - ra merőleges sajátvektornak felel meg, a Rayleigh-reláció segítségével határozható meg :

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

ahol

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

a vektor euklideszi normája . $v\in \mathbb {R} ^{n}$

Ennek a definíciónak a normalizált változatát is széles körben használják, és kényelmesebb bizonyos eredmények eléréséhez. Ebben az esetben a mátrixot tekintjük , amely a G gráf átmeneti mátrixa . Minden sajátértéke −1 és 1 között van. Ha a gráf nem szabályos, a gráf spektruma hasonló módon definiálható a Kirchhoff-mátrix sajátértékei segítségével . Irányított gráf esetén az A konjugációs mátrix szinguláris értékeit használjuk, amelyek megegyeznek az A T A szimmetrikus mátrix sajátértékeinek négyzetgyökével . ${\tfrac {1}{d}}A$

A különböző típusú kiterjesztések közötti kapcsolat

A fenti kiterjesztési típusok összefüggenek egymással. Különösen bármely d -reguláris G gráf esetén,

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

Ezért az állandó fokú gráfoknál a csúcs- és élbővítés nagysága egyenlő.

Cheeger egyenlőtlenségei

Abban az esetben, ha G egy d -reguláris gráf, akkor összefüggés van h ( G ) és G spektrális d − λ 2 hézaga között . Egy Tanner által, illetve függetlenül Noga Alon és Vitali Milman [8] által levezetett egyenlőtlenség kimondja, hogy [9]

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

Ez az egyenlőtlenség szorosan összefügg a Markov-láncok Cheeger -korlátjával , és a Riemann-geometriában a Cheeger-egyenlőtlenség diszkrét változataként fogható fel .

Hasonló összefüggést vizsgálnak a csúcsizoperimetriás számok és a spektrális rés között [10] . Vegyük észre, hogy a cikkben szereplő λ 2 itt 2( d − λ 2 )-nek felel meg

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

Aszimptotikusan a , és számokat felülről a spektrális rés határolja . ${\frac {h^{2}}{d}}$ $h_{\text{out}}$ $h_{\text{in}}^{2}$ $O(d-\lambda _{2})$

Épületek

Három fő stratégia létezik a kiterjesztési gráfcsaládok létrehozására [11] . Az első stratégia algebrai és csoportelméleti, a második analitikus, additív kombinatorika segítségével , a harmadik pedig kombinatorikus, a cikk-cakk szorzatot és a kapcsolódó kombinatorikus szorzatokat használja.

Margulis - Gabber - Galil

A Cayley-gráfokon alapuló algebrai konstrukció az expanderek különféle változatairól ismert. A következő konstrukció Margulisnak köszönhető, és Gabber és Galil elemezte [12] . Bármely természetes n -re felállítunk egy gráfot, G n csúcskészlettel , ahol . Bármely csúcsnak nyolc szomszédja lesz ${\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)).

A következő tétel érvényes:

Tétel. Minden n esetén a G n gráf második legnagyobb sajátértéke kielégíti az egyenlőtlenséget . $\lambda (G)\leq 5{\sqrt {2))$

Ramanujan gróf

Alon (Alon) és Boppana (Boppana) tétele alapján minden kellően nagy d -reguláris gráfra érvényes az egyenlőtlenség , ahol λ a második sajátérték abszolút értékben [13] . Ramanujan gráfokhoz [14] . Így a Ramanujan gráfok aszimptotikusan a lehető legkisebb λ értékkel rendelkeznek, és kiváló spektrumbővítők. $\lambda \geq 2{\sqrt {d-1}}-o(1)$ $\lambda \leq 2{\sqrt {d-1))$

Alexander Lubotsky, Philips és Sarnak (1988), Margulis (1988) és Morgenstern (1994) megmutatták, hogyan lehet a Ramanujan gráfot explicit módon megszerkeszteni [15] . Friedman tétele szerint (Friedman, 2003) egy n csúcsú véletlenszerű d-reguláris gráf majdnem Ramanujan gráf, mivel

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

valószínűséggel [ 16 ] . $1-o(1)$ $n\rightarrow \infty$

Alkalmazások és hasznos funkciók

Kezdetben az expanderek iránti érdeklődés egy stabil hálózat (telefonok vagy számítógépek) kiépítése érdekében merült fel - a korlátozott szabályszerűségi értékű bővítési gráfok íveinek száma lineárisan nő a csúcsok számához képest.

A bővítőket széles körben használják a számítógépek és rendszerek elméletében, algoritmusok felépítésében , korrekciós kódokban , kivonatokban , pszeudo-véletlenszám-generátorokban , rendezési hálózatokban [17] és számítógépes hálózatokban . A számítási komplexitáselmélet számos fontos eredményének bizonyítására is használják őket, mint például az SL = L [18] és a PCP-tétel [19] . A kriptográfiában a bővítőket hash függvények létrehozására használják .

Az alábbiakban a bővítők néhány olyan tulajdonságát mutatjuk be, amelyeket számos területen hasznosnak tartanak.

A keverő lemma

A keverési lemma kimondja, hogy a csúcsok bármely két részhalmaza esetén az S és T közötti élek száma megközelítőleg megegyezik egy véletlenszerű d - reguláris gráf éleinek számával. A közelítés jobb, minél kisebb . Véletlenszerű d -reguláris gráfban, valamint élkiválasztási valószínűségű véletlenszerű Erdős-Rényi gráfban S és T közötti élek várhatók . $S,T\subseteq V$ ${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\))$ ${\tfrac {d}{n))$ ${\tfrac {d}{n}}\cdot |S|\cdot |T|$

Formálisabban jelölje E ( S , T ) az S és T közötti élek számát . Ha ez a két halmaz metszi egymást, akkor a metszéspontban lévő íveket kétszer számoljuk, így

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

A keverési lemma kimondja, hogy [20]

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

ahol λ a normalizált második legnagyobb sajátérték abszolút értéke.

Bilu és Linial nemrég kimutatta, hogy ennek fordítva is igaz, vagyis a lemma egyenlőtlensége miatt a második legnagyobb sajátérték [21] . $O(d\lambda \cdot (1+\log(1/\lambda )))$

Expander Wanderings

A Chernoff-korlát szerint, ha a [−1, 1] intervallumból sok független véletlen értéket választunk, nagy valószínűséggel, a kiválasztott értékek átlaga közel lesz a véletlen matematikai elvárásához. változó. Az expander walk lemma Ajtari, Komlosh és Szemedy [22] és Gilman [23] szerint azt állítja, hogy ugyanez igaz az expander sétákra is. Ez hasznos a derandomizációs elméletben , mivel az expander walk sokkal kevesebb véletlenszerű bitet használ, mint egy véletlenszerű független minta.

Lásd még

Jegyzetek

↑ AMS, 2006 .
↑ Gashkov, 2009 .
↑ AMS, 2006 , Definíció 2.1.
↑ Bobkov 12 , 2000 .
↑ AlonCapalbo, 2002 .
↑ AMS, 2006 , 2.3.
↑ AMS, 2006 A spektrális rés definíciója a 2.3.
↑ AlonSpencer, 2011 .
↑ AMS, 2006 , 2.4. Tétel.
↑ Bobkov, 2000 , 1. tétel a 156. oldalon.
↑ Yehudayoff, 2012 .
↑ Goldreich, 2011 , lásd például 9. o.
↑ AMS, 2006 , 2.7. Tétel.
↑ AMS, 2006 , Definíció 5.11.
↑ AMS, 2006 , 5.12. Tétel.
↑ AMS, 2006 , 7.10. tétel.
↑ ACM, 1983 .
↑ Reingold, 2008 .
↑ Dinur, 2007 .
↑ A keverési lemma magyarázata. [egy]
↑ Fordított állítás a keverési lemmára. [2]
↑ ACM, 1987 .
↑ Gillman, 1998 .

Irodalom

Könyvek

SB Gashkov, Expander gráfok és alkalmazásaik a kódoláselméletben. — M .: MTsNMO , 2009. — S. 70–122. — (Matematikai oktatás, harmadik sorozat).

Noga Alon, Joel Spencer. A valószínűségi módszer. — 3. – John Wiley & Sons , 2011.
Chung, Fan R. K. Spektrális gráf elmélet. - American Mathematical Society , 1997. - V. 92. - (CBMS regionális konferenciasorozat a matematikában). — ISBN 0-8218-0315-8 .
Guiliana Davidoff, Peter Sarnak, Alain Valette. Elemi számelmélet, csoportelmélet és Ramanujan gráfok. - Cambridge University Press , 2003. - V. 55. - ISBN 0-521-53143-8 .
Mike Krebs, Anthony. Bővítőcsaládok és Cayley-grafikonok: Útmutató kezdőknek. - Oxford University Press , 2011. - ISBN 0-19-976711-4 .

Kutatási cikkek

Alon, N.; Capalbo, M. Explicit egyedi szomszédos bővítők // The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings .. - 2002. - 73. o .

Shlomo Hoory, Nathan Linial, Avi Widgerson. Expander gráfok és alkalmazásaik // Bulletin (New series) of the American Mathematical Society. - 2006. - T. 43 , sz. 4 . – S. 439–561 . - doi : 10.1090/S0273-0979-06-01126-8 .
Bobkov S., Houdré C., Tetali P. λ ∞ , vertex izoperimetria és koncentráció // Combinatorica. - 2000. - T. 20 , sz. 2 . – S. 153–172 . - doi : 10.1007/s004930070018 . .

Ajtai Miklós, Komlós János, Szemerédi Endre. 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. Szemedi. 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. A PCP tétel réserősítéssel // Journal of the ACM. - 2007. - T. 54 , sz. 3 . - S. 12 . - doi : 10.1145/1236457.1236459 . .
D. Gillman. A Chernoff által kötött véletlenszerű séták a bővítő grafikonokon // SIAM Journal on Computing. - Ipari és Alkalmazott Matematikai Társaság, 1998. - V. 27 , sz. 4, . - S. 1203-1220 . - doi : 10.1137/S0097539794268765 .
Oded Goldreich. Alapvető tények az Expander Graphsról // Tanulmányok a komplexitásról és a kriptográfiáról. - 2011. - S. 451-464 . - doi : 10.1007/978-3-642-22670-0_30 .
Omer Reingold. Irányítatlan kapcsolat a naplótérben // Az ACM naplója . - 2008. - T. 55 , sz. 4 . - doi : 10.1145/1391289.1391291 .
Yehudayoff, Amir. A bővítés bizonyítása három lépésben. - 2012. - T. 43 , sz. 3 . – 67–84 . - doi : 10.1145/2421096.2421115 .