Expandera graf - Expander graph

I kombinatorik är en expanderdiagram ett gles diagram som har starka anslutningsegenskaper , kvantifierade med hjälp av vertex- , kant- eller spektralutvidgning. Expander-konstruktioner har skapat forskning inom ren och tillämpad matematik, med flera tillämpningar på komplexitetsteori , design av robusta datornätverk och teorin om felkorrigeringskoder .

Definitioner

Intuitivt är ett expanderdiagram ett ändligt, oriktat multigrafi där varje delmängd av hörn som inte är "för stor" har en "stor" gräns . Olika formaliseringar av dessa begrepp ger upphov till olika uppfattningar om expanderare: kantutvidgare , vertexutvidgare och spektralutvidgare , såsom definieras nedan.

En bortkopplad graf är inte en expanderare, eftersom gränsen för en ansluten komponent är tom. Varje ansluten graf är en expander; emellertid har olika anslutna grafer olika expansionsparametrar. Den kompletta grafen har den bästa expansionen egendom, men det har största möjliga utsträckning. Informellt är en graf en bra expanderare om den har låg grad och höga expansionsparametrar.

Kantutvidgning

Den kant expansionen (även isoperimetriska nummer eller Cheeger konstant ) h ( G ) hos en graf G på n vertex definieras som

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

var ${\ displaystyle \ partial S: = \ {\ {u, v \} \ i E (G) \: \ u \ i S, v \ i V (G) \ setminus S \}.}$

I ekvationen är det minsta över alla nonempty uppsättningar S av högst n / 2 hörn och ∂ S är den kantgränsen av S , dvs den uppsättning av kanter med exakt en slutpunkt i S .

Vertex expansion

Den vertex isoperimetriska antal (även vertex expansionen eller förstoring ) av en graf G definieras som ${\ displaystyle h _ {\ text {out}} (G)}$

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

där är den yttre gränsen av S , dvs den uppsättning av hörn i med åtminstone en granne i S . I en variant av denna definition (som kallas unik granne expansions ) är ersatt med en uppsättning hörn i V med exakt en granne i S . ${\ displaystyle \ partial _ {\ text {out}} (S)}$${\ displaystyle V (G) \ setminus S}$${\ displaystyle \ partial _ {\ text {out}} (S)}$

Den vertex isoperimetriska antal av en graf G definieras som ${\ displaystyle h _ {\ text {in}} (G)}$

${\ displaystyle 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 , dvs uppsättningen av hörn i S med minst en granne i . ${\ displaystyle \ partial _ {\ text {in}} (S)}$${\ displaystyle V (G) \ setminus S}$

Spektral expansion

När G är d -regelbunden är en linjär algebraisk definition av expansion möjlig baserat på egenvärdena för angränsningsmatrisen A = A ( G ) för G , var är antalet kanter mellan hörn i och j . Eftersom A är symmetrisk , det spektralsatsen innebär att A har n real-värderade egenvärden . Det är känt att alla dessa egenvärden finns i [- d , d ]. ${\ displaystyle A_ {ij}}$${\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}}$

Eftersom G är regelbunden, den likformiga fördelningen med för alla i = 1, ..., n är den stationära fördelningen av G . Det vill säga att vi har Au = du och u är en egenvektor av A med egenvärde λ ₁ = d , där d är graden för G-hörnpunkterna . Den spektrala gapet av G definieras som d  - λ ₂ , och den mäter den spektrala expansionen av grafen G . ${\ displaystyle u \ in \ mathbb {R} ^ {n}}$${\ displaystyle u_ {i} = 1 / n}$

Det är känt att λ _n = - d om och endast om G är bipartit. I många sammanhang, till exempel i expanderblandningslemma , räcker det inte med en bunden på λ ₂ , men det är verkligen nödvändigt att binda det absoluta värdet av alla egenvärden bort från d :

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

Eftersom detta är den största egenvärdet som motsvarar en egenvektor ortogonal till u , kan den definieras ekvivalent med Rayleigh-kvoten :

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

var

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

är vektorn 2-norm . ${\ displaystyle v \ in \ mathbb {R} ^ {n}}$

De normaliserade versionerna av dessa definitioner används också i stor utsträckning och är mer praktiska för att ange några resultat. Här man betraktar matrisen , vilket är den Markov övergångsmatris av grafen G . Dess egenvärden ligger mellan −1 och 1. För inte nödvändigtvis vanliga diagram kan spektrumet för en graf definieras på liknande sätt med hjälp av egenvärdena för den laplaciska matrisen . För riktade grafer, anser man de singulära värdena av grannmatris A , som är lika med rötterna av egenvärdena för den symmetriska matrisen A ^T A . ${\ displaystyle {\ tfrac {1} {d}} A}$

Förhållanden mellan olika expansionsegenskaper

Expansionsparametrarna som definierats ovan är relaterade till varandra. I synnerhet för alla d -regelbundna diagram G ,

${\ displaystyle h _ {\ text {out}} (G) \ leq h (G) \ leq d \ cdot h _ {\ text {out}} (G).}$

Följaktligen, för grafer med konstant grad, är vertex- och kantutvidgning kvalitativt densamma.

Cheeger ojämlikheter

När G är d -regular, det finns ett samband mellan det isoperimetriska konstant h ( G ) och gapet d - λ ₂ i spektrumet för den adjacency operatören av G . Enligt standardspektralgrafteori är trivial egenvärde för adjacensoperatören för en d -regelbunden graf λ ₁ = d och den första icke-triviella egenvärdet är λ ₂ . Om G är ansluten, då λ ₂ < d . En ojämlikhet på grund av Dodziuk och oberoende Alon och Milman säger att

${\ displaystyle {\ 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-gränsen för Markov-kedjor och kan ses som en diskret version av Cheegers ojämlikhet i Riemannian-geometri .

Liknande samband mellan vertex-isoperimetriska tal och spektralgapet har också studerats:

${\ displaystyle h _ {\ text {out}} (G) \ leq \ left ({\ sqrt {4 (d- \ lambda _ {2})}} + 1 \ right) ^ {2} -1}$

${\ displaystyle h _ {\ text {in}} (G) \ leq {\ sqrt {8 (d- \ lambda _ {2})}}.}$

Asymptotiskt sett är kvantiteterna , och alla begränsade ovan av spektralgapet . ${\ displaystyle {\ frac {h ^ {2}} {d}}}$${\ displaystyle h _ {\ text {out}}}$${\ displaystyle h _ {\ text {in}} ^ {2}}$${\ displaystyle O (d- \ lambda _ {2})}$

Konstruktioner

Det finns tre allmänna strategier för att konstruera familjer med expanderdiagram. Den första strategin är algebraisk och gruppteoretisk, den andra strategin är analytisk och använder additiv kombinatorik , och den tredje strategin är kombinatorisk och använder sicksack och relaterade grafprodukter. Noga Alon visade att vissa grafer konstruerade från ändliga geometrier är de sparsamaste exemplen på starkt expanderande grafer.

Margulis – Gabber – Galil

Algebraiska konstruktioner baserade på Cayley-grafer är kända för olika varianter av expanderdiagram. Följande konstruktion beror på Margulis och har analyserats av Gabber och Galil. För varje naturligt tal n , anser man grafen G _n med vertex set , där : för varje vertex , dess åtta närliggande hörn är ${\ displaystyle \ mathbb {Z} _ {n} \ times \ mathbb {Z} _ {n}}$${\ displaystyle \ mathbb {Z} _ {n} = \ mathbb {Z} / n \ mathbb {Z}}$${\ displaystyle (x, y) \ in \ mathbb {Z} _ {n} \ times \ mathbb {Z} _ {n}}$

${\ displaystyle (x \ pm 2y, y), (x \ pm (2y + 1), y), (x, y \ pm 2x), (x, y \ pm (2x + 1)).}$

Sedan gäller följande:

Sats. För alla n , grafen G _n har näst största egenvärdet . ${\ displaystyle \ lambda (G) \ leq 5 {\ sqrt {2}}}$

Ramanujan grafer

Med en sats om Alon och Boppana uppfyller alla tillräckligt stora d -regelbundna grafer , var är det näst största egenvärdet i absolut värde. Ramanujan-grafer är d- vanliga grafer för vilka denna gräns är tät och tillfredsställande . Därför har Ramanujan-grafer ett asymptotiskt minsta möjliga värde på . Detta gör dem till utmärkta spektralutvidgare. ${\ displaystyle \ lambda _ {2} \ geq 2 {\ sqrt {d-1}} - o (1)}$${\ displaystyle \ lambda _ {2}}$${\ displaystyle \ lambda = \ max _ {| \ lambda _ {i} | <d} | \ lambda _ {i} | \ leq 2 {\ sqrt {d-1}}}$${\ displaystyle \ lambda _ {2}}$

Lubotzky , Phillips och Sarnak (1988), Margulis (1988) och Morgenstern (1994) visar hur Ramanujan-grafer kan konstrueras uttryckligen. Enligt en sats om Friedman (2003) är slumpmässiga d -regelbundna grafer på n hörn nästan Ramanujan, det vill säga de uppfyller

${\ displaystyle \ lambda \ leq 2 {\ sqrt {d-1}} + \ varepsilon}$

för alla med sannolikhet som n tenderar till oändlighet. ${\ displaystyle \ varepsilon> 0}$${\ displaystyle 1-o (1)}$

Tillämpningar och användbara egenskaper

Den ursprungliga motivationen för expanderare är att bygga ekonomiska robusta nätverk (telefon eller dator): en expander med begränsad valens är just ett asymptotiskt robust diagram med antalet kanter som växer linjärt med storlek (antal hörn), för alla delmängder.

Expanderdiagram har hittat omfattande tillämpningar inom datavetenskap , vid utformning av algoritmer , felkorrigeringskoder , extraherare , pseudorandomgeneratorer , sorteringsnätverk ( Ajtai, Komlós & Szemerédi (1983) ) och robusta datornätverk . De har också använts i bevis på många viktiga resultat i beräkningskomplexitetsteori , såsom SL  =  L ( Reingold (2008) ) och PCP-satsen ( Dinur (2007) ). I kryptografi används expanderdiagram för att konstruera hashfunktioner .

Expandera blandningslemma

Expanderblandningslemmet säger att antalet kanter mellan S och T är ungefär vad du förväntar dig i ett slumpmässigt d- regelbundet diagram för två underuppsättningar av topparna S , T ⊆ V. Uppskattningen är bättre ju mindre är. I en slumpmässig d -regular graf, såväl som i en Erdős-Renyi slumpgraf med kant sannolikhet d / n , förväntar vi kanterna mellan S och T . ${\ displaystyle \ lambda = \ max \ {| \ lambda _ {2} |, | \ lambda _ {n} | \}}$${\ displaystyle {\ tfrac {d} {n}} \ cdot | S | \ cdot | T |}$

Mer formellt, låt E ( S , T ) betecknar antalet kanter mellan S och T . Om de två uppsättningarna inte är separerade räknas kanterna i deras korsning två gånger, det vill säga

${\ displaystyle E (S, T) = 2 | E (G [S \ cap T]) | + E (S \ setminus T, T) + E (S, T \ setminus S).}$

Sedan säger expanderblandningslemmet att följande ojämlikhet gäller:

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

Provtagning av expanderpromenader

Den Tjernoff bundna anges att, när provtagning många oberoende prover från en slumpvariabler inom intervallet [-1, 1], med hög sannolikhet genomsnittet av våra prover, ligger nära den förväntan om den stokastiska variabeln. Expandera promenadprovtagningslemma, på grund av Ajtai, Komlós & Szemerédi (1987) och Gillman (1998) , säger att detta också gäller vid provtagning från en promenad på en expanderdiagram. Detta är särskilt användbart i teorin om derandomisering , eftersom sampling enligt en expanderpromenad använder många färre slumpmässiga bitar än sampling oberoende av varandra.

Se även

• Algebraisk anslutning
• Sicksackprodukt
• Superstark approximation
• Teori om spektralgraf

Anteckningar

Referenser

externa länkar

• Kort introduktion i Notices of the American Mathematical Society
• Inledning av Michael Nielsen
• Föreläsningsanteckningar från en kurs om expanderare (av Nati Linial och Avi Wigderson)
• Föreläsningsanteckningar från en kurs om expanderare (av Prahladh Harsha)
• Definition och tillämpning av spektralgap