Cheeger-állandó (gráfelmélet)

A matematikában a gráf Cheeger-állandója ( Cheeger-szám vagy izoperimetrikus szám is ) a gráf numerikus jellemzője, amely tükrözi, hogy a gráfnak van-e szűk keresztmetszete vagy sem. A Cheeger-konstans a "szűk keresztmetszetek" jelenlétének mérésére számos területen érdekes, például erősen összekapcsolt számítógépes hálózatok létrehozása , kártyák keverése és az alacsony dimenziós topológiában (különösen a hiperbolikusság tanulmányozásában). 3-dimenziós elosztók [1] ). Jeff Cheeger matematikusról nevezték el .

Definíció

Legyen egy irányítatlan gráf csúcsok és ívek halmazával . Legyen a csúcsok halmaza azon ívek halmaza, amelyek a halmaz csúcsait a [2] -hez nem tartozó csúcsokkal kötik össze : $G$ $V(G)$ $E(G)$ $A\subseteq V(G)$ $\ részleges A$ $A$ $A$

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

Emlékezzünk vissza, hogy az ívek nem irányítottak, tehát az ív megegyezik az ívvel . $(x, y)$ $(y,x)$

Ekkor a gráf Cheeger-állandóját (jelöljük ) a következőképpen definiáljuk $G$ $h(G)$

h(G):=\min \left\{\left.{\frac {|\partial A|}{|A|}}\right|A\subseteq V(G),0<|A| \leqslant {\frac {|V(G)|}{2}}\right\}.

A Cheeger-állandó akkor és csak akkor pozitív, ha a gráf össze van kapcsolva . Intuitív módon világos, hogy ha a Cheeger-állandó kicsi, de pozitív, akkor a gráfban van egy "szűk keresztmetszet", abban az értelemben, hogy két "nagy" csúcshalmaz van, amelyek között "kis" számú kapcsolat (ív) található. A Cheeger-konstans „nagy”, ha egy csúcshalmaz két részhalmazra való felosztása „nagy” számú kapcsolatot hagy ezen részhalmazok között. $G$

Példa: számítógépes hálózat

Képzelje el, hogy olyan hálózati konfigurációt kell kifejlesztenie, amelyben a Cheeger-állandó nagy (legalábbis jelentősen különbözik a nullától), még akkor is, ha | V ( G )| (a számítógépek száma a hálózaton) nagy.

Például N ≥ 3 számítógép van egyesülve egy gyűrűben , és egy G N gráfot alkotnak . Számozzuk meg a gyűrűben az óramutató járásával megegyező irányban lévő 1, 2, ..., N számokkal rendelkező számítógépeket. Matematikai szempontból van egy sok csúcsú gráf

V(G_{N}):=\{1,2,\dots ,N\}

és sok ív

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

Vegyük ezeket a számítógépeket a láncban A halmazként : $\lfloor N/2\rfloor$

A:=\{1,2,\dots ,\lfloor N/2\rfloor \}.

Ez egyértelmű

\partial A=\{(\lfloor N/2\rfloor ,\lfloor N/2\rfloor +1),(N,1)\},

így

{\frac {|\partial A|}{|A|}}={\frac {2}{\lfloor N/2\rfloor }}\ to 0

nál nél

N\to \infty .

Ez a példa Cheeger h ( G N ) állandójának felső korlátját mutatja , és nullára hajlik, ahogy N a végtelenbe megy. Ezért egy gyűrűben összekapcsolt számítógépek hálózatát tekinthetjük úgy, mint amely folyamatos "szűk keresztmetszetekből" áll nagy N esetén, és ez gyakorlati értelemben érthető. Amint egy számítógép meghibásodik a ringben, az árfolyam meredeken csökken. Ha két nem csatlakoztatott számítógép meghibásodik, a hálózat két nem csatlakoztatott részre szakad.

Cheeger egyenlőtlensége

A Cheeger-állandó különösen fontos a bővítőgráfok kontextusában , mivel méri, hogy egy gráfot hogyan fednek le az ívei. Az úgynevezett Cheeger-egyenlőtlenség a spektrális réshez kapcsolódik, és tartalmazza a Cheeger-állandót.

Lásd még

Jegyzetek

↑ Lackenby, 2010 , 7. § Geometriai és topológiai invariánsok viselkedése véges fedésekben, p. 13.
↑ Lubotzky, 2011 , 1. fejezet: Bővítő gráfok. 1.1 Alapvető definíciók. P.5.

Irodalom

Donetti, L., Neri, F., and Muñoz, M. Optimális hálózati topológiák: bővítők, ketrecek, Ramanujan gráfok, összefonódott hálózatok és mindez // J. Stat. Mech. - 2006. - T. 2006 , szám. 08 . - doi : 10.1088/1742-5468/2006/08/P08007 .
Lackenby, M. Heegaard hasítások, a virtuálisan Haken sejtés és tulajdonság (τ) // Invent. Math. - 2006. - T. 164 , sz. 2 . - S. 317-359 . - doi : 10.1007/s00222-005-0480-x .
Mark Lackenby. 3-sokaság véges fedőterei // Proceedings of the International Congress of Mathematicians. Hyderabad, India. – 2010.
Lubotzky Sándor. Expander Graphs in Pure and Applied Mathematics // Ez a tanulmány az Amerikai Matematikai Társaság (AMS) és az Amerikai Matematikai Szövetség (MAA) közös éves találkozóján tartott kollokviumi előadásokra készült jegyzeteken alapul. – 2011.