Cheegerova konstanta (teorie grafů)

V matematice je Cheegerova konstanta (také Cheegerovo číslo nebo izoperimetrické číslo ) grafu numerickou charakteristikou grafu, která odráží, zda má graf „úzké hrdlo“ nebo ne. Cheegerova konstanta jako způsob měření přítomnosti „úzkého hrdla“ je zajímavá v mnoha oblastech, například pro vytváření vysoce propojených počítačových sítí , pro míchání karet a v nízkorozměrné topologii (zejména při studiu hyperbolického 3-rozměrné rozdělovače [1] ). Pojmenováno po matematikovi Jeffu Cheegerovi .

Definice

Dovolit být neorientovaný graf se sadou vrcholů a oblouků . Nechť pro množinu vrcholů znamená množinu všech oblouků spojujících vrcholy množiny s vrcholy, které nepatří do [2] : $G$ $V(G)$ $E(G)$ $A\subseteq V(G)$ $\část A$ $A$ $A$

\partial A:=\{(x,y)\in E(G)\mid x\in A,y\in V(G)\setminus A\}.

Připomeňme, že oblouky nejsou směrovány, takže oblouk je stejný jako . $(x, y)$ $(y,x)$

Potom je Cheegerova konstanta grafu (označená ) definována jako $G$ $h(G)$

h(G):=\min \left\{\left.{\frac {|\částečné A|}{|A|}}\right|A\subseteq V(G),0<|A| \leqslant {\frac {|V(G)|}{2}}\right\}.

Cheegerova konstanta je striktně kladná právě tehdy, když je graf souvislý . Je intuitivně jasné, že pokud je Cheegerova konstanta malá, ale kladná, je v grafu „úzké hrdlo“ v tom smyslu, že existují dvě „velké“ množiny vrcholů s „malým“ počtem vazeb (oblouků). Cheegerova konstanta je „velká“, pokud jakékoli rozdělení množiny vrcholů na dvě podmnožiny zanechá „velký“ počet spojení mezi těmito podmnožinami. $G$

Příklad: počítačová síť

Představte si, že potřebujete vyvinout konfiguraci sítě, ve které je konstanta Cheeger velká (alespoň výrazně odlišná od nuly), i když | V ( G )| (počet počítačů v síti) je velký.

Například existuje N ≥ 3 počítačů sdružených do kruhu , které tvoří graf G N . Očíslujme počítače čísly 1, 2, ..., N v kroužku ve směru hodinových ručiček. Z matematického hlediska existuje graf s mnoha vrcholy

V(G_{N}):=\{1,2,\tečky ,N\}

a mnoho oblouků

E(G_{N}):=\{(1,2),(2,3),\tečky ,(N-1,N),(N,1)\}.

Vezměme tyto počítače v řetězci jako sadu A : $\lfloor N/2\rfloor$

A:=\{1,2,\tečky ,\lpatro N/2\rpatro \}.

To je jasné

\partial A=\{(\lpatro N/2\rpatro ,\lpatro N/2\rpatro +1),(N,1)\},

tak

{\frac {|\částečné A|}{|A|}}={\frac {2}{\lpodlaží N/2\rpodlaží }}\to 0

N\to \infty .

Tento příklad ukazuje horní mez Cheegerovy konstanty h ( G N ) a má tendenci k nule, když N jde do nekonečna. Síť počítačů zapojených do kruhu tedy můžeme považovat za souvislou „úzká hrdla“ pro velká N , což je v praktickém smyslu pochopitelné. Jakmile selže jeden počítač v ringu, kurz prudce klesne. Pokud selžou dva nepropojené počítače, síť se rozdělí na dvě nepropojené části.

Cheegerova nerovnost

Cheegerova konstanta je zvláště důležitá v kontextu expandérových grafů , protože slouží jako míra toho, jak je graf pokryt svými oblouky. Takzvaná Cheegerova nerovnost souvisí se spektrální mezerou a obsahuje Cheegerovu konstantu.

Viz také

Poznámky

↑ Lackenby, 2010 , §7 Chování geometrických a topologických invariantů v konečných obalech, str. 13.
↑ Lubotzky, 2011 , Kapitola 1. Rozšiřující grafy. 1.1 Základní definice. P.5.

Literatura

Donetti, L., Neri, F., and Muñoz, M. Optimální topologie sítí: expandéry, klece, Ramanujanovy grafy, provázané sítě a vše ostatní // J. Stat. Mech. - 2006. - T. 2006 , vydání. 08 . - doi : 10.1088/1742-5468/2006/08/P08007 .
Lackenby, M. Heegaard rozdělení, virtuálně Hakenův dohad a vlastnost (τ) // Invent. Matematika. - 2006. - T. 164 , č. 2 . - S. 317-359 . - doi : 10.1007/s00222-005-0480-x .
Mark Lackenby. Konečné krycí prostory 3-variet // Sborník příspěvků z Mezinárodního kongresu matematiků. Hyderabad, Indie. — 2010.
Alexandr Lubotzky. Expander Graphs in Pure and Applied Mathematics // Tento příspěvek je založen na poznámkách připravených pro přednášky z kolokvia na společném výročním zasedání Americké matematické společnosti (AMS) a Americké matematické asociace (MAA). — 2011.