Cayley-gráf

A Wikipédiából, a szabad enciklopédiából
Az a és b elemekkel generált szabad csoport egy Cayley-gráfja

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.

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 gG elem megfelel egy vgV csúcsnak a gráfban.
  2. Minden sS elem megfelel egy cs színnek.
  3. Minden gG és sS esetében a vg és a vgs csúcsok között létezik egy cs 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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

  • 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 Zn × Zm 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 D4 diédercsoport Cayley-gráfja az a és b generátorokkal
  • A D4 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 D4 Cayley-táblázata származtatható a következő csoportprezentációból
 \langle a, b | a^4 = b^2 = e, a b = b a^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ó[szerkesztés | forrásszöveg szerkesztése]

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 hG 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 v1 ∈ V(Γ) csúcsot, és színezzük meg c1-gyel! Ez meghatározza Γ minden további v csúcsának színét, mivel egyértelműen van egy g elem, ami v1-et v-be viszi. Az S generátorhalmaz a v1 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Cayley-komplexusok[szerkesztés | forrásszöveg szerkesztése]

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 Z2 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 Z2 csoport Cayley-gráfja.

Schreier-gráfok[szerkesztés | forrásszöveg szerkesztése]

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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

  1. Csúcstranzitív gráf
  2. Generátorhalmaz
  3. Lovász-sejtés
  4. Generátorhalmaz

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  • 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.