Cheegerin vakio (graafiteoria)

Matematiikassa graafin Cheeger -vakio (myös Cheeger-luku tai isoperimetrinen luku ) on graafin numeerinen ominaisuus, joka heijastaa sitä, onko kaaviolla "pullonkaula" vai ei. Cheegerin vakio tapa mitata "pullonkaula" on kiinnostava monilla aloilla, esimerkiksi luotaessa erittäin yhteenliitettyjä tietokoneverkkoja , korttien sekoittamisessa ja pieniulotteisessa topologiassa (erityisesti hyperbolisen toiminnan tutkimuksessa 3-ulotteiset jakoputket [1] ). Nimetty matemaatikko Jeff Cheeger mukaan .

Määritelmä

Antaa olla suuntaamaton graafi, jossa on joukko pisteitä ja kaaria . Olkoon kärkijoukolla joukko kaaria, jotka yhdistävät joukon kärjet pisteisiin, jotka eivät kuulu ryhmään [2] : $G$ $V(G)$ $E(G)$ $A\subseteq V(G)$ $\osittainen A$ $A$ $A$

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

Muista, että kaaria ei ole suunnattu, joten kaari on sama kaari kuin . $(x, y)$ $(y,x)$

Sitten graafin Cheeger-vakio (merkitty ) määritellään seuraavasti $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\}.

Cheegerin vakio on ehdottomasti positiivinen , jos ja vain jos graafi on yhdistetty . On intuitiivisesti selvää, että jos Cheegerin vakio on pieni mutta positiivinen, graafissa on "pullonkaula" siinä mielessä, että on kaksi "suuria" kärkijoukkoja, joiden välillä on "pieni" määrä linkkejä (kaareja). Cheegerin vakio on "suuri", jos mikä tahansa kärkijoukon jakaminen kahdeksi osajoukoksi jättää "suuren" määrän yhteyksiä näiden osajoukkojen välille. $G$

Esimerkki: tietokoneverkko

Kuvittele, että sinun on kehitettävä verkkokonfiguraatio, jossa Cheeger-vakio on suuri (ainakin merkittävästi erilainen kuin nolla), vaikka | V ( G )| (verkossa olevien tietokoneiden määrä) on suuri.

Esimerkiksi N ≥ 3 tietokonetta on yhdistetty renkaaseen muodostaen graafin G N . Numeroidaan tietokoneet numeroilla 1, 2, ..., N renkaassa myötäpäivään. Matemaattiselta kannalta katsottuna on graafi, jossa on monia pisteitä

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

ja monia kaaria

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

Otetaan nämä ketjussa olevat tietokoneet joukkona A : $\lfloor N/2\rfloor$

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

Se on selvää

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

niin

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

klo

N\to \infty .

Tämä esimerkki näyttää Cheegerin vakion h ( G N ) ylärajan, ja se pyrkii nollaan, kun N menee äärettömään. Siksi voidaan pitää renkaaseen kytkettyjen tietokoneiden verkkoa jatkuvana "pullonkaulona" suurelle N :lle , ja tämä on käytännössä ymmärrettävää. Heti kun yksi kehässä oleva tietokone epäonnistuu, valuuttakurssi laskee jyrkästi. Jos kaksi yhdistämätöntä tietokonetta epäonnistuu, verkko jakautuu kahteen yhdistämättömään osaan.

Cheegerin epätasa-arvo

Cheegerin vakio on erityisen tärkeä laajennuskaavioiden yhteydessä , koska se mittaa, kuinka kaavio peittyy sen kaareilla. Niin kutsuttu Cheegerin epäyhtälö liittyy spektrirakoon ja sisältää Cheegerin vakion.

Katso myös

Muistiinpanot

↑ Lackenby, 2010 , §7 Geometristen ja topologisten invarianttien käyttäytyminen äärellisissä kansissa, s. 13.
↑ Lubotzky, 2011 , Luku 1. Laajennuskaaviot. 1.1 Perusmääritelmät. P.5.

Kirjallisuus

Donetti, L., Neri, F., ja Muñoz, M. Optimaaliset verkkotopologiat: laajentimet, häkit, Ramanujan-graafit, kietoutuvat verkot ja kaikki muu // J. Stat. Mech. - 2006. - T. 2006 , numero. 08 . - doi : 10.1088/1742-5468/2006/08/P08007 .
Lackenby , M. Heegaard halkeamat, virtuaalisesti Hakenin arvelu ja ominaisuus (τ) // Invent. Matematiikka. - 2006. - T. 164 , no. 2 . - S. 317-359 . - doi : 10.1007/s00222-005-0480-x .
Mark Lackenby. 3-monijoukon rajalliset peittävät tilat // Proceedings of the International Congress of Mathematicians. Hyderabad, Intia. – 2010.
Aleksanteri Lubotzky. Expander Graphs in Pure and Applied Mathematics // Tämä artikkeli perustuu muistiinpanoihin, jotka on tehty American Mathematical Societyn (AMS) ja Mathematical Association of America:n (MAA) yhteisen vuosikokouksen kollokvion luentoihin. – 2011.