Expander (teorie grafů)

Expander (z anglického expander graph - expanding graph) je silně propojený řídký graf , přičemž konektivitu lze určovat pomocí vrcholů, oblouků nebo spektra (viz níže) [1] .

Historie

Studium expandérů iniciovali moskevští matematici M. S. Pinsker , L. A. Bassalygo a G. A. Margulis v sedmdesátých letech XX. V minulosti našly tyto grafy mnoho neočekávaných aplikací, například v teorii výpočetní složitosti a v teorii kódování. Ukázalo se také, že jsou propojeny s úseky moderní matematiky, které mají ke klasické teorii grafů daleko, např. s teorií grup a teorií čísel a jsou v současnosti předmětem aktivního výzkumu, prováděného především zahraničními matematiky. Bibliografie na toto téma zahrnuje stovky publikací [2] .

Definice

Expandér je konečný neorientovaný multigraf , ve kterém je jakákoli podmnožina vrcholů, i když není "příliš velká", "silně" spojena. Různé formalizace těchto konceptů poskytují různé typy expandérů: expandér hran , expandér vrcholů a spektrální expandér .

Odpojený graf není expandér. Každý připojený graf je expandér, ale různé připojené grafy mají různé parametry expandéru. Kompletní graf má nejlepší parametry expandéru, ale má nejvyšší možný stupeň. Neformálně řečeno, graf je dobrý expandér, pokud má nízký stupeň a vysoký parametr expandéru.

Rozšíření žeber

Rozšíření hrany (také isoperimetrické číslo nebo Cheegerova konstanta ) h ( G ) grafu G pro n vrcholů je definováno jako

h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\částečné (S)|}{|S|}},

kde minimum přebírá všechny neprázdné množiny S nejvýše n /2 vrcholů a ∂( S ) jsou hraniční oblouky množiny S , tedy množiny oblouků s jediným vrcholem v S [3] .

Rozšíření vertexu

Isoperimetrické číslo vrcholu (také rozšíření vrcholu ) grafu G je definováno jako $h_{\text{out}}(G)$

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

kde je vnější hranice S , tedy množiny vrcholů , které mají alespoň jednoho souseda v S [4] . Ve variantě této definice (nazývané jedinečné rozšíření sousedů ), je ) nahrazeno množinou vrcholů z V s právě jedním sousedem z S [5] . $\partial _{\text{out}}(S)$ $V(G)\setminus S$ $\partial _{\text{out}}(S)$

Isoperimetrické číslo vrcholu grafu G je definováno jako $h_{\text{in}}(G)$

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

kde je vnitřní hranice S , tedy množina vrcholů S , které mají alespoň jednoho souseda v [4] . $\partial _{\text{in}}(S)$ $V(G)\setminus S$

Spektrální expanze

Pokud je G d - regulární , je možné definovat pomocí lineární algebry na základě vlastních hodnot matice sousednosti A = A ( G ) grafu G , kde je počet oblouků mezi vrcholy i a j [ 6] . Protože A je symetrický , podle spektrální věty má A n skutečných vlastních čísel . Je známo, že tyto hodnoty leží v intervalu [− d , d ]. $A_{{ij}}$ ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n))$

Graf je regulární právě tehdy, když vektor c pro všechna i = 1, …, n je vlastním vektorem matice A a jeho vlastní hodnota je konstantní mocninou grafu. Máme tedy Au = du a u je vlastní vektor matice A s vlastními čísly λ 1 = d , kde d je stupeň vrcholů grafu G . Spektrální mezera grafu G je definována jako d −λ 2 a je mírou spektrální expanze grafu G [7] . $u\in \mathbb {R} ^{n}$ $u_{i}=1$

Je známo, že λ n = − d právě tehdy, když G je bipartitní. V mnoha případech, například ve směšovacím lemmatu , je nutné zdola omezit nejen mezeru mezi λ 1 a λ 2 , ale také mezeru mezi λ 1 a druhým maximálním vlastním číslem v absolutní hodnotě:

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

Protože tato vlastní hodnota odpovídá nějakému vlastnímu vektoru ortogonálnímu k u , lze ji určit pomocí Rayleighova vztahu :

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

kde

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

je euklidovská norma vektoru . $v\in \mathbb {R} ^{n}$

Normalizovaná verze této definice je také široce používána a je vhodnější pro získání určitých výsledků. V tomto případě uvažujeme matici , což je přechodová matice grafu G . Všechna jeho vlastní čísla leží mezi −1 a 1. Pokud graf není pravidelný, lze spektrum grafu definovat podobným způsobem pomocí vlastních čísel Kirchhoffovy matice . Pro orientovaný graf se používají singulární hodnoty konjugační matice A , které se rovnají odmocninám vlastních hodnot symetrické matice A TA . ${\tfrac {1}{d}}A$

Vztah mezi různými typy rozšíření

Výše uvedené typy rozšíření spolu souvisí. Zejména pro jakýkoli d -regulární graf G ,

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

Proto pro grafy konstantního stupně jsou vrcholová a okrajová rozšíření stejná.

Cheegerovy nerovnosti

V případě, že G je d - regulární graf, existuje vztah mezi h ( G ) a spektrální mezerou d − λ 2 G . Nerovnost odvozená Tannerem a nezávisle Noga Alon a Vitali Milman [8] uvádí, že [9]

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

Tato nerovnost úzce souvisí s Cheegerovou vazbou pro Markovovy řetězce a lze ji považovat za samostatnou verzi Cheegerovy nerovnosti v Riemannově geometrii .

Podobný vztah mezi vrcholovými izoperimetrickými čísly a spektrální mezerou je také studován [10] . Všimněte si, že λ 2 v článku odpovídá 2 ( d − λ 2 ) zde

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

Asymptoticky jsou čísla , a ohraničena shora spektrální mezerou . ${\frac {h^{2}}{d}}$ $h_{\text{out}}$ $h_{\text{in}}^{2}$ $O(d-\lambda _{2})$

Budovy

Existují tři hlavní strategie pro vytváření rodin rozšiřujících grafů [11] . První strategie je algebraická a grupově teoretická, druhá je analytická s použitím aditivní kombinatoriky a třetí je kombinatorická s použitím klikatého součinu a přidružených kombinatorických součinů.

Margulis - Gabber - Galil

Algebraická konstrukce založená na Cayleyových grafech je známá pro různé varianty expandérů. Následující konstrukce je dílem Margulis a byla analyzována Gabberem a Galilem [12] . Pro libovolné přirozené n sestavíme graf G n s množinou vrcholů , kde . Pro jakýkoli vrchol bude jeho osm sousedů ${\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 (2r+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).

Platí následující věta:

Teorém. Pro všechna n druhá největší vlastní hodnota grafu G n vyhovuje nerovnosti . $\lambda (G)\leq 5{\sqrt {2))$

Hrabě Ramanujan

Podle věty Alona (Alon) a Boppany (Boppana) pro všechny dostatečně velké d - regulární grafy platí nerovnost , kde λ je druhé vlastní číslo v absolutní hodnotě [13] . Pro Ramanujanovy grafy [14] . Ramanujanovy grafy tedy mají asymptoticky nejmenší možnou hodnotu λ a jsou vynikajícími spektrálními expandéry. $\lambda \geq 2{\sqrt {d-1}}-o(1)$ $\lambda \leq 2{\sqrt {d-1))$

Alexander Lubotsky, Philips a Sarnak (1988), Margulis (1988) a Morgenstern (1994) ukázali, jak lze Ramanujanův graf explicitně sestavit [15] . Podle Friedmanovy věty (Friedman, 2003) je náhodný d-regulární graf s n vrcholy téměř Ramanujanovým grafem, protože

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

s pravděpodobností na [16] . $1-o(1)$ $n\rightarrow \infty$

Aplikace a užitečné funkce

Zpočátku zájem o expandéry vznikl za účelem vybudování stabilní sítě (telefony nebo počítače) - počet oblouků grafů rozšíření s omezenou hodnotou pravidelnosti roste lineárně s ohledem na počet vrcholů.

Expandéry jsou široce používány v teorii počítačů a systémů, pro konstrukci algoritmů , v opravných kódech , extraktorech , generátorech pseudonáhodných čísel , třídicích sítích [17] a počítačových sítích . Používají se také k prokázání mnoha důležitých výsledků v teorii výpočetní složitosti , jako je SL = L [18] a PCP teorém [19] . V kryptografii se expandéry používají k vytváření hashovacích funkcí .

Níže jsou uvedeny některé vlastnosti expandérů, které jsou považovány za užitečné v mnoha oblastech.

Směšovací lemma

Směšovací lemma říká, že pro libovolné dvě podmnožiny vrcholů je počet hran mezi S a T přibližně roven počtu hran v náhodném d - regulárním grafu. Aproximace je lepší, tím menší . V náhodném d - regulárním grafu, stejně jako v náhodném Erdős-Rényiho grafu s pravděpodobností výběru hran , se očekávají hrany mezi S a T . $S,T\subseteq V$ ${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\))$ ${\tfrac {d}{n))$ ${\tfrac {d}{n}}\cdot |S|\cdot |T|$

Formálněji, nechť E ( S , T ) označuje počet hran mezi S a T . Pokud se tyto dvě množiny protnou, oblouky v průsečíku se započítají dvakrát, takže

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

Směšovací lemma říká, že [20]

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

kde λ je absolutní hodnota normalizovaného druhého největšího vlastního čísla.

Bilu a Linial nedávno ukázali, že platí i obráceně, to znamená, že vzhledem k nerovnosti v lemmatu je druhé největší vlastní číslo [21] . $O(d\lambda \cdot (1+\log(1/\lambda )))$

Expander Toulky

Podle Chernoffovy meze , pokud vybereme mnoho nezávislých náhodných hodnot z intervalu [−1, 1], s vysokou mírou pravděpodobnosti se průměr vybraných hodnot bude blížit matematickému očekávání náhodného variabilní. Lemma chůze s expandérem podle Ajtariho, Komloshe a Szemeredyho [22] a Gilmana [23] uvádí, že totéž platí pro chůze s expandérem. To je užitečné v teorii derandomizace , protože procházka expandéru používá mnohem méně náhodných bitů než náhodný nezávislý vzorek.

Viz také

Poznámky

↑ AMS, 2006 .
↑ Gashkov, 2009 .
↑ AMS, 2006 , Definice 2.1.
↑ 12 Bobkov, 2000 .
↑ AlonCapalbo, 2002 .
↑ AMS, 2006 , část 2.3.
↑ AMS, 2006 Definice spektrální mezery převzata z části 2.3.
↑ AlonSpencer, 2011 .
↑ AMS, 2006 , Věta 2.4.
↑ Bobkov, 2000 , Věta 1 na str. 156.
↑ Yehudayoff, 2012 .
↑ Goldreich, 2011 , viz např. str. 9.
↑ AMS, 2006 , Věta 2.7.
↑ AMS, 2006 , Definice 5.11.
↑ AMS, 2006 , Věta 5.12.
↑ AMS, 2006 , Věta 7.10.
↑ ACM, 1983 .
↑ Reingold, 2008 .
↑ Dinur, 2007 .
↑ Vysvětlení lemmatu míchání. [jeden]
↑ Obraťte tvrzení k lemmatu míchání. [2]
↑ ACM, 1987 .
↑ Gillman, 1998 .

Literatura

knihy

SB Gashkov, Expandérové grafy a jejich aplikace v teorii kódování. — M .: MTsNMO , 2009. — S. 70–122. — (Matematická výchova, třetí řada).

Noga Alon, Joel Spencer. Pravděpodobnostní metoda. — 3. — John Wiley & Sons , 2011.
Chung, Fan R. K. Teorie spektrálních grafů. - American Mathematical Society , 1997. - V. 92. - (CBMS Regional Conference Series in Mathematics). — ISBN 0-8218-0315-8 .
Guiliana Davidoff, Peter Sarnak, Alain Valette. Elementární teorie čísel, teorie grup a Ramanujanovy grafy. - Cambridge University Press , 2003. - V. 55. - ISBN 0-521-53143-8 .
Mike Krebs, Anthony. Rozšiřte rodiny a Cayleyho grafy: Průvodce pro začátečníky. - Oxford University Press , 2011. - ISBN 0-19-976711-4 .

Výzkumné články

Alon, N.; Capalbo, M. Explicit unique-neighbor expanders // The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings .. - 2002. - S. 73 .

Shlomo Hoory, Nathan Linial, Avi Widgerson. Rozšiřující grafy a jejich aplikace // Bulletin (nová řada) Americké matematické společnosti. - 2006. - T. 43 , no. 4 . — S. 439–561 . - doi : 10.1090/S0273-0979-06-01126-8 .
Bobkov S., Houdré C., Tetali P. λ ∞ , vrcholová izoperimetrie a koncentrace // Combinatorica. - 2000. - T. 20 , no. 2 . — S. 153–172 . - doi : 10.1007/s004930070018 . .

Miklós Ajtai, János Komlós, Endre Szemerédi. Sborník příspěvků z 15. výročního sympozia ACM o teorii výpočetní techniky . - 1983. - S. 1-9 . - ISBN 0-89791-099-0 . - doi : 10.1145/800061.808726 .
M. Ajtai,J. Komlos, E. Szemeredi. Sborník příspěvků z 19. výročního sympozia ACM o teorii výpočetní techniky // ACM. - 1987. - S. 132-140 . — ISBN 0-89791-221-7 . - doi : 10.1145/28395.28410 .
Irit Dinur. Věta PCP pomocí zesílení mezery // Journal of the ACM. - 2007. - T. 54 , č. 3 . - S. 12 . - doi : 10.1145/1236457.1236459 . .
D. Gillman. Chernoff Bound for Random Walks on Expander Graphs // SIAM Journal on Computing. - Společnost pro průmyslovou a aplikovanou matematiku, 1998. - V. 27 , no. 4, . - S. 1203-1220 . - doi : 10.1137/S0097539794268765 .
Oded Goldreich. Základní fakta o rozšiřujících grafech // Studie složitosti a kryptografie. - 2011. - S. 451-464 . - doi : 10.1007/978-3-642-22670-0_30 .
Omer Reingold. Nepřímá konektivita v log-space // Journal of the ACM . - 2008. - T. 55 , no. 4 . - doi : 10.1145/1391289.1391291 .
Yehudayoff, Amire. Prokázání expanze ve třech krocích. - 2012. - T. 43 , č. 3 . — s. 67–84 . - doi : 10.1145/2421096.2421115 .