Cayley-gráf

A matematikában azon gráfokat nevezik Cayley-gráfoknak, amelyek egy csoport struktúráját reprezentálják. A Cayley-gráfok központi szerepet játszanak a kombinatorikában és a geometriai csoportelméletben. Arthur Cayley brit matematikus nevét őrzi az elnevezés.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitív	${\boldsymbol {\rightarrow }}$	távolságreguláris	${\boldsymbol {\leftarrow }}$	erősen reguláris
${\boldsymbol {\downarrow }}$
szimmetrikus	${\boldsymbol {\leftarrow }}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\boldsymbol {\downarrow }}$
(ha összefüggő) csúcs- és éltranzitív	${\boldsymbol {\rightarrow }}$	éltranzitív és reguláris	${\boldsymbol {\rightarrow }}$	éltranzitív
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
csúcstranzitív	${\boldsymbol {\rightarrow }}$	reguláris	${\boldsymbol {\rightarrow }}$	(ha páros) bireguláris
${\boldsymbol {\uparrow }}$
Cayley-gráf	${\boldsymbol {\leftarrow }}$	zérószimmetrikus		aszimmetrikus

Az a és b elemekkel generált szabad csoport egy Cayley-gráfja

Adott $G$ csoport és $S$ generátorhalmaz esetében a Cayley-gráf a következő színezett, irányított gráf:

1. Minden g ∈ G elem megfelel egy v_g ∈ V csúcsnak a gráfban.
2. Minden s ∈ S elem megfelel egy c_s színnek.
3. Minden g ∈ G és s ∈ S esetében a v_g és a v_gs csúcsok között létezik egy c_s színű él.

A geometriai csoportelméletben általában felteszik, hogy az S generátorhalmaz véges és szimmetrikus (azaz S = S^-1) és nem tartalmazza a csoport neutrális elemét. Ebben az esetben G egy hurokélektől mentes irányítatlan gráf.

Elemi tulajdonságok

• Egy adott csoporthoz tartozó Cayley-gráf nem egyértelmű, mert egy adott csoport generátorhalmaza sem egyértelmű.
• Ha a generátorhalmaz n elemű, akkor minden csúcsból pontosan n él indul ki és pontosan n él érkezik minden csúcsba. Ha a generátorhalmaz szimmetrikus, azaz minden elemének inverzét is tartalmazza, akkor reguláris gráf keletkezik.
• Ha a generátorhalmaz tartalmazza az egységelemet, akkor minden csúcsra illeszkedik hurokél, ezért gyakran már a definícióban megkövetelik, hogy a generátorhalmaz ne tartalmazza az egységelemet.
• A Cayley-gráf körei megfelelnek a csoport elemei közötti relációknak.
• Ha $f:G'\to G$ szürjektív homomorfizmus, ami injektív G’ S’ generátorhalmazán, akkor f a

${\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad$ ahol S = f(S’)

gráf fedését indukálja.

• Ha a G csoportot n generátor generálja, amik egyike sem önmaga inverze, és az S generátorhalmaz szimmetrikus, akkor a Γ(G,S) Cayley-gráf lefedhető az S generátorhalmazhoz tartozó szabad csoporthoz tartozó 2n fokú végtelen fával, a 2n fokú Bethe-ráccsal.

• Ha az S részhalmaz nem generátorrendszer, akkor is elkészíthető a Γ(G,S) gráf, de ez nem lesz összefüggő, és nem tekintik Cayley-gráfnak. Ekkor Γ(G,S) minden összefüggőségi komponense megfelel az S által generált részcsoport egy mellékosztályának.

Példák

• Ha $G=(\mathbb {Z} ,+)$ az egész számok csoportja az összeadás műveletre nézve a generátorhalmaz pedig $S=\{1,-1\}$, akkor a Cayley-gráf egy végtelen lánc.
• Hasonlóan ha $G=(\mathbb {Z} _{n},+)$ az n elemű véges, ciklikus csoport, a generátorhalmaz pedig a csoport standard generátoreleméből és annak inverzéből áll, akkor a Cayley-gráf pontosan a $C_{n}$ körgráf.
• Két csoport direkt szorzatának Cayley-gráfja azonos a csoportok Cayley-gráfjainak direkt szorzatával. Ezért a $\mathbb {Z} ^{2}$ Abel-csoport a (±1, ±1) négyelemű generátorhalmazzal a végtelen síkbeli rácsgráfot generálja, a Z_n × Z_m direkt szorzat hasonló generátorhalmazzal a $C_{n}\times C_{m}$ gráfot (az $n\times m$ tórikus rácsgráfot) generálja.

A D₄ diédercsoport Cayley-gráfja az a és b generátorokkal

• A D₄ diédercsoport Cayley-gráfja az a and b generátorokkal jobboldalt látható. A piros nyilak mutatják a balról való szorzást az a elemmel. Mivel b önmaga inverze, a kék élek, amelyek a balról b-val szorzást jelölik, irányítatlanok. A gráf vegyes: 8 csúcsa van, 8 irányított éle, és 4 irányítatlan éle. A D₄ Cayley-táblázata származtatható a következő csoportprezentációból

$\langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle .$

• Az a, b elemekkel generált szabad csoport az S = {a, b, a^‒1, b^‒1} generátorhalmazzal a cikk tetején szereplő Cayley-gráfot implikálja. A neutrális elemet az e betű jelzi. Egy élen jobbra lépés a-val való szorzást jelent, egy felfelé lépés a b-vel való szorzást. Ez a körmentes Cayley-gráf kulcsfontosságú a Banach–Tarski-paradoxon bizonyításában.

Karakterizáció

Mikor lehet egy adott gráf egy csoport Cayley-gráfja?

Hasson a G csoport önmagán balról szorzással! Ez a hatás hatás lesz a Cayley-gráfon is. Konkrétan, a h ∈ G elem a g ∈ V(Γ) csúcsot a hg ∈ V(Γ) csúcsba küldi. Hasonlóan, a (g,gs) él a (hg,hgs) élbe megy át. A balról szorzás (egyszeresen) tranzitív hatás; ennek megfelelően a Cayley-gráf csúcstranzitív.

Eszerint:

A Γ gráf akkor és csak akkor Cayley-gráfja a G csoportnak, ha Γ automorfizmuscsoportja tartalmazza G egy (egyszeresen) tranzitív hatását. Azaz, ha van homomorfizmus a G csoportból Γ automorfizmuscsoportjába.

A színezés rekonstrukciójához válasszunk egy v₁ ∈ V(Γ) csúcsot, és színezzük meg c₁-gyel! Ez meghatározza Γ minden további v csúcsának színét, mivel egyértelműen van egy g elem, ami v₁-et v-be viszi. Az S generátorhalmaz a v₁ csúcs szomszédainak színéhez tartozó elemekből fog állni. S akkor és csak akkor lesz véges, ha Γ lokálisan véges, vagyis minden csúcsnak véges sok szomszédja van.

Megfordítva azonban nem igaz, hogy minden csúcstranzitív gráf egy G csoport egy Cayley-gráfja, és a fenti tétel nem válaszolja meg a Cayley-gráfok struktúrájának összes kérdését. Például még nincs bizonyítva Lovász László sejtése, hogy minden Cayley-gráf tartalmaz Hamilton-kört.

Csoportelméleti vonatkozások

A Cayley-gráf szomszédsági mátrixának vizsgálatával, különösen a spektrális gráfelmélet eredményeit felhasználva, következtetni lehet a csoport szerkezetére.

Geometriai csoportelmélet

A geometriai csoportelméletben a végtelen csoportok jellemzésére alapvető fontosságú a Cayley-gráf durva geometriája, vagy annak kváziizometriai ekvivalenciaosztálya. Végesen generált csoportokra ez független a generátorrendszer választásától, tehát a csoport tulajdonságának tekinthető. Ez véges csoportok esetén érdektelen, ugyanis ezek kváziizometrikusak az egy pontból álló térrel, hiszen a generátorcsoport választható az egész csoportnak.

A Cayley-gráf egy csoport metrikus képe a szómetrikával. Ezt a generátorok egyértelműen meghatározzák.

Rokon konstrukciók

Cayley-komplexusok

A Cayley-komplexus cellakomplexus, aminek 1-váza a Cayley-gráf, de 2-cellákkal is el van látva. A 2-cellákhoz relátorokra is szükség van úgy, hogy az S generátorhalmaz és a relátorok R halmaza együtt a csoport prezentációját adja.

Például a Z² csoport Cayley-komplexusa a $\langle \alpha ,\beta |\alpha \beta \alpha ^{-1}\beta ^{-1}=e\rangle$ prezentációval a sík egységnégyzetekkel való parkettázása, aminek 1-váza a Z² csoport Cayley-gráfja.

Schreier-gráfok

A Schreier-gráf a Cayley-gráf általánosítása. Egy G csoport Schreier-gráfjának megadásához a generátorokon kívül egy részcsoportot is rögzíteni kell; jelölje ezt a részcsoportot H! Ekkor a Σ(G,H,S) Schreier-gráf csúcsai megfelelnek a H-val vett jobb mellékosztályoknak, élei a Cayley-gráf éleinek. Maga a Cayley-gráf az a Schreier-gráf, amit a H=1 triviális részcsoport ad.

Kapcsolódó szócikkek

• Csúcstranzitív gráf
• Generátorhalmaz
• Lovász-sejtés

Fordítás

• Ez a szócikk részben vagy egészben a Cayley graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.