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:

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

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] .

A G gráf csúcs izoperimetrikus számát a következőképpen definiáljuk

ahol S belső határa ,  vagyis S azon csúcsainak halmaza , amelyeknek legalább egy szomszédja van a [4]-ben .

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 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] .

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:

.

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 :

ahol

a vektor euklideszi normája .

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 .

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,

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]

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

Aszimptotikusan a , és számokat felülről a spektrális rés határolja .

É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

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 .

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.

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

valószínűséggel [ 16 ] .

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 .

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

.

A keverési lemma kimondja, hogy [20]

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] .

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

  1. AMS, 2006 .
  2. Gashkov, 2009 .
  3. AMS, 2006 , Definíció 2.1.
  4. Bobkov 12 , 2000 .
  5. AlonCapalbo, 2002 .
  6. AMS, 2006 , 2.3.
  7. AMS, 2006 A spektrális rés definíciója a 2.3.
  8. AlonSpencer, 2011 .
  9. AMS, 2006 , 2.4. Tétel.
  10. Bobkov, 2000 , 1. tétel a 156. oldalon.
  11. Yehudayoff, 2012 .
  12. Goldreich, 2011 , lásd például 9. o.
  13. AMS, 2006 , 2.7. Tétel.
  14. AMS, 2006 , Definíció 5.11.
  15. AMS, 2006 , 5.12. Tétel.
  16. AMS, 2006 , 7.10. tétel.
  17. ACM, 1983 .
  18. Reingold, 2008 .
  19. Dinur, 2007 .
  20. A keverési lemma magyarázata. [egy]
  21. Fordított állítás a keverési lemmára. [2]
  22. ACM, 1987 .
  23. Gillman, 1998 .

Irodalom

Könyvek

Kutatási cikkek

Linkek