Cayley gráfok izomorfizmus problémája

Mező József

Témavezető: Pálfy Péter Pál egyetemi tanár

Eötvös Loránd Tudományegyetem Budapest, 2005

Tartalomjegyzék

1. Bevezetés 2

2. Cayley-gráfok 4 2.1. Cayley-gráfok és néhány izomorfizmus probléma . . . . . . . . . . . . . . . 4 2.2. Példák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. CI-gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4. CI-csoportok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3. (D)CI-csoportok 10 3.1. Ciklikus gráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. Általános eset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4. Az elemi Abel csoportok esete 14 4.1. G-invariáns partíciók . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2. Koszorú reláció . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3. Cayley segédgráfok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.4. A segédgráfok módszere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1. fejezet

Bevezetés

A gráfelmélet egyik alapvető problémája két adott gráfról eldönteni, hogy izomorfak-e. Szakdolgozatomban ezt a problémát vizsgálom Cayley-gráfokra. Az első két fejezet ennek áttekintése, és bevezető jellegű a többi fejezethez, támaszkodva Cai Heng Li [13] összefoglaló cikkére és Pálfy Péter Pál egy akadémiai előadására.

A Cayley-gráfok csúcsai egy G véges csoport elemeinek felelnek meg, az adjacencia relációt pedig egy S ⊆ G csatlakozó halmaz segítségével definiáljuk. A. Cayley 1878-ban absztrakt csoportok egy gráfreprezentációjaként vezette be az olyan típusú diagramot, amit ma Cayley színezett diagram-nak nevezünk. Ezt Coxeter és Moser [10] használták előszőr generátorokkal és relációkkal megadott csoportok vizsgálatára. A Cayley színezett diagram egy irányított gráf színezett élekkel, és akkor lesz belőle Cayley-gráf, ha elhagyjuk a színeket. A Cayley színezett diagramok általánosítása a Schreier mellékosztály diagramok, amit Schreier vezetett be 1927-ben. Ezeket mint gráfokat előszőr Sabidussi [25] vizsgálta. A Cayley-gráfok és általánosításaik, a csúcstranzitív gráfok vizsgálata hosszú ideje aktív téma az algebrai gráfelméletben, lásd [7], [8] és [24].

A Cayley-gráfok izomorfiaosztályaival kapcsolatos kutatások 1967-ben kezdődtek Ádám Andrásnak [1] a Journal of Combinatorial Theory probléma-rovatában közzétett kérdésével. Azt sejtette, hogy két ciklikus gráf pontosan akkor izomorf, ha van közöttük olyan izomorfizmus is, ami egyúttal a hozzájuk tartozó ciklikus csoportnak egy automorfizmusa. Más szavakkal egy ciklikus csoport minden Cayley-gráfja CI-gráf. Sejtésére már 1970-ben ellenpéldát talált B. Elspas és J. Turner [11], azonban a teljes válasz csak 30 évvel a probléma megfogalmazása után született meg. M. Muzychuk [19] és [20] a Schur-gyűrűk elméletét felhasználva bebizonyította, hogy azokra az esetekre, amelyekre addig nem találtak ellenpéldát, a sejtés már igaz:

1.1 TÉTEL. Ádám András sejtése pontosan akkor igaz, ha n négyzetmentes szám, vagy egy páratlan négyzetmentes szám négyszerese. Irányítatlan gráfokra igaz akkor is, ha n = 8, 9 vagy 18.

Időközben a problémát több irányban általánosították. Kézenfekvő, hogy ciklikus csoport helyett tetszőleges véges csoport Cayley-gráfjaira általánosítsuk a problémát, gráfok helyett pedig tetszőleges relációstruktúrákat is tekinthetünk. Ezt a kétirányú általánosítást 1977-ben fogalmazta meg Babai László [4]. A G alaphalmazú ℜ relációstruktúra Cayleyobjektum, ha az összes jobb-eltolás automorfizmusa ℜ-nek. ℜ CI-objektum, ha minden vele izomorf Cayley-objektumba átvihető egy csoport automorfizmussal is. Egy G csoportot globálisan CI-csoportnak nevezünk, ha minden Cayley-objektuma CI-objektum. 1987-ben a véges egyszerű csoportok osztályozásának egy nevezetes következményét, a kétszeresen tranzitív permutációcsoportok teljes leírását felhasználva Pálfy Péter Pál [23] meghatározta az összes ilyen csoportot:

1.2 TÉTEL. A véges globálisan CI-csoportok a következők: azok a ciklikus csoportok, amelyeknek n rendjére (n, φ(n)) = 1 teljesül, továbbá a 4-elemű csoportok. Ha egy csoport nem globálisan CI-csoport, akkor van olyan Cayley-objektuma, ami egyetlen négyváltozós relációból áll és nem CI-objektum.

Egy G véges csoportot DCI-csoportnak nevezünk, ha minden irányított Cayley-gráfja CIgráf és CI-csoportnak, ha minden irányítatlan Cayley-gráfja CI-gráf. Muzychuk tétele (1.1) megadja, hogy a ciklikus csoportok közül melyek az ilyen csoportok. Könnyű látni, hogy CIcsoport minden részcsoportja is CI-csoport. Ezt (is) használva még 1978-ban Babai László és Frankl Péter [5] meghatározták, hogy mely csoportok lehetnek Sylow-részcsoportok egy CI-csoportban:

1.3 TÉTEL. CI-csoport Sylow részcsoportja vagy elemi Abel-féle p-csoport (azaz Z_{p}^{k}), vagy Z_{4}, Z_{8}, Q, Z_{9} valamelyike.

A kérdés tehát az, hogy mely elemi Abel-csoportok, azaz mely Z_{p}^{k} csoportok CI-csoportok. A Schur-gyűrűk módszerével 2001-ben Hirasaka és Muzychuk [12] belátták, hogy Z_{p}^{4} DCIcsoport, majd 2003-ban Muzychuk [21] megmutatta, hogy Z_{p}^{k} nem DCI-csoport, ha k (p-től függően) elég nagy. Irányított esetben tehát a következő a kérdés:

1.4 PROBLÉMA. Van-e minden k-hoz olyan p páratlan prím, hogy Z_{p}^{k} DCI-csoport?

Még 1992-ben L. A. Nowitz [22] megmutatta, hogy Z_{2}^{6} nem CI-csoport, 1998-ban pedig Conder és Li [9] számítógép segítségével látták be, hogy Z_{2}^{5} CI-csoport. Ha p ≠ 2, akkor csak annyit tudunk, hogy Z_{p}^{4} CI-csoport, tehát a következő kérdésre sem született még válasz:

1.5 PROBLÉMA. Van-e minden p páratlan prímhez olyan k, hogy Z_{p}^{k} nem CI-csoport?

A negyedik fejezetben Joy Morris egy közelmúltban megjelent cikkéből [18] kiindulva az elemi Abel esetet tárgyalom teljes részletességgel. Ennek során különféle segédgráfok használatával elemi bizonyítást adok a Z_{p}^{4} esetre. Ezúton is szeretném megköszönni témavezetőmnek, Pálfy Péter Pálnak az érdekes témát, a sok értékes megjegyzést és segítséget.

Cayley-gráfok

2.1. Cayley-gráfok és néhány izomorfizmus probléma

Az alábbiakban G mindig egy véges csoport, S ⊆ G egy részhalmaz.

2.1 DEFINÍCIÓ. A (G, S) párhoz tartozó Cayley gráfnak nevezzük és Cay(G, S)-sel jelöljük azt a Γ irányított gráfot, amelynek csúcsai G elemei és x-ből pontosan akkor vezet él y-ba, ha yx^{−1} ∈ S. Ekkor Γ-t a G csoport egy Cayley-gráfjának, S-et pedig a Γ Cayley-gráf csatlakozó halmazának mondjuk.

Cay(G, S) tehát egy |S| -reguláris irányított Γ gráf, ahol

V (Γ) = G, E(Γ) = {(g, sg) : g ∈ G, s ∈ S}

Ha minden (g, sg) élnek megfeleltetünk egy s színt, akkor színezett Cayley-gráfot, ha pedig S egy generátorrendszer és minden s színt különbözőnek választunk, akkor Cayley színezett diagrammot kapunk. Megjegyzés. Néhány egyszerű észrevétel:

(i) Az S halmaz pontosan akkor tartalmazza G egységelemét, ha Cay(G, S) minden csúcsnál tartalmaz hurokélt. Ezért a továbbiakban feltesszük, hogy e ∉ S.

(ii) ⟨S⟩ = G pontosan akkor, ha Cay(G, S) összefüggő.

(iii) Ha S = S^{−1}, azaz ∀s ∈ S -re s^{−1} ∈ S, akkor Cay(G, S) irányítatlan gráfnak tekinthető.

Egy alapvető probléma a Cayley-gráfok izomorfizmusproblémája:

2.2 PROBLÉMA. Legyen Cay(G, S) és Cay(H, T) két adott Cayley-gráf. Döntsük el, hogy Cay(G, S) ≅ Cay(H, T)?

Most legyen Γ egy tetszőleges (reguláris) irányított gráf.

2.3 DEFINÍCIÓ. A Γ irányított gráfot Cayley-gráfnak nevezük, ha ∃ hozzá egy (G, S) pár, melyre Γ ≅ Cay(G, S). Ezt a (G, S) párt pedig a Γ gráf egy Cayley reprezentációjának nevezzük.

Γ két Cayley reprezentációja Cay(G, S) és Cay(H, T) ekvivalens, ha ∃σ ∈ Sym(V), amely izomorfizmust indukál a G csoportból a H csoportba és S^{σ} = T. Speciálisan Γ két Cayley reprezentációja, Cay(G, S) és Cay(G, T) pontosan akkor ekvivalens, ha S^{σ} = T valamely σ ∈ Aut(G)-re. Adódik a következő kérdés:

2.4 PROBLÉMA. (Gráfok Cayley reprezentációs problémája) Határozzuk meg Γ összes nem ekvivalens Cayley reprezentációját.

2.5 PÉLDA. Legyen Γ = K_{n} az n pontú irányítatlan teljes gráf. Ekkor Γ ≅ Cay(G, S), ahol G egy tetszőleges n rendű csoport, S pedig G összes nem egységelemeinek halmaza. Ezért Γ nem ekvivalens Cayley reprezentációinak száma egyenlő a nemizomorf n rendű csoportok számával.

A Γ = (V, E) irányított gráf automorfizmuscsoportjának nevezzük és AutΓ-val jelöljük az adjacencia relációt tartó σ ∈ Sym(V) permutációk halmazát. Legyen Γ=Cay(G, S). Jelölje g_{R} a g ∈ G-vel való jobb-eltolást, G_{R} pedig G jobb-eltolásainak csoportját:

G_{R} = {g_{R} : g ∈ G}, ahol x^{g_{R}} = xg ∀x ∈ V.

Hasonlóan definiálható G bal-eltolásainak csoportja:

G_{L} = {g_{L} : g ∈ G}, ahol x^{g_{L}} = gx ∀x ∈ V.

Ha yx^{−1} ∈ S, akkor yg(xg)^{−1} = yx^{−1} ∈ S, így G_{R} ≤ Aut Γ. Minden x, y ∈ V -hez egyértelműen létezik egy g_{R} = x_{R}^{−1}y_{R} ∈ G_{R} elem, melyre x^{g_{R}} = y, ezért G_{R} reguláris részcsoportja Aut Γ-nek. Tehát igazak a következők:

• A Cayley-gráfok csúcstanzitív gráfok

• Ha Cay(G, S) nem összefüggő, akkor minden komponens izomorf egy kisebb Cayleygráffal: Cay(⟨S⟩, S)-el.

• Cay(G, S) ≅ Cay(G, T) ⟺ Cay(⟨S⟩, S) ≅ Cay(⟨T ⟩, T)

Ha Γ a G csoport egy Cayley-gráfja, akkor Aut Γ-nak van egy G-vel izomorf reguláris részcsoportja: G_{R}. Ennél több is igaz:

2.6 TÉTEL. (Sabidussi [25]) Egy Γ irányított gráf pontosan akkor lesz a G csoport egy Cayley-gráfja, ha Aut Γ tartalmaz egy G-vel izomorf és V -n reguláris részcsoportot.

Bizonyítás. Ha Γ = Cay(G, S), akkor az előzőek szerint G_{R} ≤ Aut Γ. Megfordítva, legyen G_{R} ≤ Aut Γ, ahol G ≅ G_{R} és g képe az izomorfizmusnál g_{R}. G_{R} reguláris, így |V | = |G|, tehát bijekció létesíthető G elemei és Γ pontjai között a következő módon.

G egységelemének feleljen meg V egy tetszőleges v_{0} pontja, majd minden g ∈ G-re g-nek a v_{0}g_{R} pont. Végül az S halmaz álljon azon G-beli elemekből, melyeknek az imént v_{0} szomszédait feleltettük meg. Ezzel Γ ≅ Cay(G, S), hiszen a fenti bijekciónál g szomszédaihoz éppen azokat a pontokat rendeltük, amiket az sg alakú elemekhez. ■

Természetes kérdések a következők:

2.7 PROBLÉMA. Legyen Γ = (V, E) egy irányított gráf.

1. Határozzuk meg Aut Γ-t és döntsük el, van-e V -n reguláris részcsoportja.

2. Határozzuk meg a Γ Cayley-gráf Aut Γ automorfizmuscsoportjának az összes V -n reguláris részcsoportját.

3. Határozzuk meg a Γ Cayley-gráf összes nem ekvivalens Cay(G, S) G-hez tartozó Cayley reprezentációját.

2.2. Példák

2.8 PÉLDA.

G = ⟨a⟩ ≅ Z_{n^{2}}, H = ⟨x, y|x^{n} = y^{2} = 1, y^{−1}xy = x^{−1}⟩ ≅ D_{2n}.

Ekkor

Cay(G, {a, a^{−1}}) ≅ C_{2n} ≅ Cay(H, {y, xy}), és Aut(C_{2n}) ≅ D_{4n}.

2.9 DEFINÍCIÓ. Jelölje K_{m;d} az irányítatlan teljes d-partíció gráfot, ahol az osztályok m eleműek. Itt pontosan akkor van összekötve két pont, ha különböző osztályból valók.

2.10 DEFINÍCIÓ. Legyen G az Ω_{1} = {x_{1}, …, x_{m}}, H pedig az Ω_{2} = {y_{1}, …, y_{n}} halmazon egy permutációcsoport. Ekkor G és H koszorú szorzatának nevezzük, és G ≀ H-val jelöljük a következő permutációcsoportot Ω_{1} × Ω_{2}-n:

G ≀ H = {(g_{1}, …, g_{n}, h) : h ∈ H, g_{i} ∈ G, i = 1, …, n}, ahol
(g_{1}, …, g_{n}, h)(x_{i}, y_{j}) = (g_{j}(x_{i}), h(y_{j})), (j = 1, …, n).

Könnyen látható, hogy AutK_{m;d} ≅ S_{m} ≀ S_{d}.

2.11 DEFINÍCIÓ. A B ⊆ V halmazt G − blokknak hívjuk, ha minden g ∈ G-re g(B) = B vagy g(B) ∩ B = ∅. Ha emellett G tranzitív permutációcsoport, akkor a B = {g(B) : g ∈ G} partíciót G-invariáns partíciónak nevezzük. Ha B G_{1}- és G_{2}-invariáns, akkor nyilván ⟨G_{1}, G_{2}⟩-invariáns, tehát erre a tulajdonságra nézve van egy M maximális részcsoport Sym(V)-ben. Ekkor B-t nevezzük M-partíciónak.

2.12 ÁLLÍTÁS. A G csoportnak pontosan akkor van egy K_{m;d}-vel izomorf Cayley-gráfja, ha G rendje md és van egy m-ed rendű részcsoportja.

Bizonyítás. Legyen Cay(G, S) ≅ K_{m;d}, valamilyen S ⊂ G-re. Nyilvánvalóan K_{m;d} dpartíciójának osztályai a csúcsok egy B AutΓ-invariáns partícióját adják. Speciálisan B G_{R}-invariáns, és B ∈ B-re a (G_{R})_{B} stabilizátor indexe G_{R}-ben d, G_{R} rendje pedig épp a csúcsok száma, azaz md. Megfordítva, legyen G_{0} ≤ G_{R} egy m rendű részcsoport. Az S halmaz legyen G_{0} komplementere. Ekkor Cay(G, S) ≅ K_{m;d}. ■

Fogalmazzuk meg ezt a permutációcsoportok nyelvén.

2.13 ÁLLÍTÁS. Legyen X ≅ S_{m} ≀ S_{d} egy imprimitív permutációcsoport az md rendű Ω halmazon. Ekkor egy G csoport pontosan akkor ágyazható be X-be Ω-n reguláris részcsoportként, ha G-nek van egy m rendű részcsoportja.

2.14 DEFINÍCIÓ. A Γ_{1} = (V_{1}, E_{1}) és Γ_{2} = (V_{2}, E_{2}) irányított gráfok Descartes-szorzata az a Γ_{1} × Γ_{2}-vel jelölt azt Γ irányított gráf, melyre:

V (Γ) = V_{1} × V_{2}, E(Γ) = {((a_{1}, a_{2}), (b_{1}, b_{2})) : (a_{1}, b_{1}) ∈ E_{1} és a_{2} = b_{2}
vagy (a_{2}, b_{2}) ∈ E_{2} és a_{1} = b_{1}}

2.15 PÉLDA.

Γ ≅ C_{n}^{d}, ahol n = 3 vagy n ≥ 5.

Ekkor

AutΓ ≅ D_{2n} ≀ S_{d} = D_{2n}^{d}S_{d}.

Ha n páratlan, akkor Γ izomorf Z_{n}^{d} egy Cayley gráfjával, ha pedig n páros, akkor egy G_{1} × G_{2} × ⋯ × G_{d} csoport Cayley-gráfjával, ahol G_{i} ≅ Z_{n} vagy D_{n}.

2.16 DEFINÍCIÓ. A Γ_{1} = (V_{1}, E_{1}) és Γ_{2} = (V_{2}, E_{2}) irányított gráfok lexikografikus szorzatának nevezzük és Γ_{1}[Γ_{2}]-vel jelöljük azt a Γ irányított gráfot, melyre:

V (Γ) = V_{1} × V_{2}, E(Γ) = {((a_{1}, a_{2}), (b_{1}, b_{2})) : (a_{1}, b_{1}) ∈ E_{1} vagy a_{1} = b_{1} és (a_{2}, b_{2}) ∈ E_{2}}

2.17 PÉLDA.

G = ⟨a⟩ ≅ Z_{n^{2}}, S = a⟨a^{n}⟩, illetve H = ⟨b, c⟩ ≅ Z_{n} × Z_{n}, T = b⟨c⟩.
Cay(G, S) ≅ C_{n}[\overline{K}_{n}] ≅ Cay(H, T),

ahol C_{n} egy irányított n hosszú kör, \overline{K_{n}} pedig az n pontú él nélküli gráf. Hasonlóan

S′ = a⟨a^{n}⟩ ∪ a^{−1}⟨a^{n}⟩, illetve T′ = b⟨c⟩ ∪ b^{−1}⟨c⟩
Cay(G, S′) ≅ C_{n}[\overline{K}_{n}] ≅ Cay(H, T′),

ahol C_{n} most egy irányítatlan n hosszú kör.

2.3. CI-gráfok

2.18 DEFINÍCIÓ. A Cay(G, S) Cayley-gráfot CI-gráfnak nevezzük, ha minden vele izomorf Cay(G, T) Cayley-gráfhoz van olyan σ ∈ Aut(G), hogy S^{σ} = T.

Érdemes a bevezetésben már említett általánosabb esetet nézni, vagyis gráfok helyett tetszőleges relációstruktúrákat vizsgálni.

2.19 DEFINÍCIÓ. Legyen G egy véges csoport. Egy G alaphalmazú ℜ relációstruktúrát G Cayley-objektumának nevezünk, ha G_{R} ≤ Aut(ℜ). Egy ℜ Cayley-objektumot CIobjektumnak hívunk, ha minden vele izomorf ℑ Cayley-objektumhoz létezik egy α ∈ Aut(G), hogy ℑ = ℜ^{α}.

A következő lemma alapvető fontosságú a különféle CI-csoportok vizsgálatában.

2.20 LEMMA. (Babai [4]) Egy G véges csoport ℜ Cayley-objektuma pontosan akkor CI-objektum, ha

φG_{R}φ^{−1} ≤ Aut(ℜ) (φ ∈ Sym(G)) ⇒ ∃ψ ∈ Aut(ℜ) : φG_{R}φ^{−1} = ψG_{R}ψ^{−1}.

Bizonyítás. Legyen ℜ CI-objektum és φG_{R}φ^{−1} ≤ Aut(ℜ) valamilyen φ ∈ Sym(G)-re Aut(ℜ^{φ}) = φ^{−1}Aut(ℜ)φ ≥ G_{R}, ezért ℜ^{φ} Cayley-objektum és létezik α ∈ Aut(G), hogy ℜ^{α} = ℜ^{φ}. ℜ^{φα^{−1}} = ℜ, ezért ψ := φα^{−1} ∈ Aut(ℜ) és φG_{R}φ^{−1} = ψαG_{R}α^{−1}ψ^{−1} = ψG_{R}ψ^{−1}.

Megfordítva, legyen ℑ is egy Cayley-objektum, φ ∈ Sym(G) izomorfizmus: ℑ = ℜ^{φ}. Aut(ℜ) = φAut(ℑ)φ^{−1} ≥ φG_{R}φ^{−1}, és a feltételből ∃ψ ∈ Aut(ℜ) : φG_{R}φ^{−1} = ψG_{R}ψ^{−1}. Legyen γ := ψ^{−1}φ, g := 1γ^{−1}, δ := g_{R}γ. Ekkor γ^{−1}G_{R}γ = δ^{−1}G_{R}δ = G_{R} és 1δ = 1. Ez a δ indukál egy α ∈ Aut(G) automorfizmust G_{R}-n: δ^{−1}g_{R}δ = (g^{α})_{R} = α^{−1}g_{R}α. Tehát δα^{−1} centralizálja G_{R}-t Sym(G)-ben. Ismert, hogy ez a centralizátor G_{L}, így δα^{−1} = id_{G}, α = δ = g_{R}γ = g_{R}ψ^{−1}φ és φ = ψg_{R}^{−1}α. Végűl ℑ = ℜ^{φ} = ℜ^{ψg_{R}^{−1}α} = ℜ^{α}. ■

2.21 LEMMA. Legyen p egy prim, G egy véges p-csoport és tegyük fel, hogy G_{R} p-Sylow részcsoportja Aut(ℜ)-nek, G valamely ℜ Cayley-objektumára. Ekkor ℜ CI-objektum.

Bizonyítás. Aut(ℜ) ≥ φ^{−1}G_{R}φ ≅ G_{R}, ezért következik Sylow II. tételéből és a 2.20 lemmából. ■

2.4. CI-csoportok

2.22 DEFINÍCIÓ. Egy G véges csoportot globálisan CI-csoportnak hívunk, ha minden Cayley-objektuma CI-objektum, DCI-csoportnak, ha minden irányított Cayley-gráfja CIgráf, és CI-csoportnak, ha minden irányítatlan Cayley-gráfja CI-gráf.

2.23 DEFINÍCIÓ. Egy G véges csoport H részcsoportját pronormálisnak nevezzük, ha ∀g ∈ G-re: g^{−1}Hg és H konjugáltak ⟨H, g^{−1}Hg⟩-ben.

2.24 ÁLLÍTÁS. Egy G véges csoport pontosan akkor lesz globálisan CI-csoport, ha G_{R} pronormális részcsoportja Sym(G)-nek.

Bizonyítás. Egy relációstruktúra izomorfizmuscsoportja tetszőleges permutációcsoport lehet, ezért minden φ ∈ Sym(G)-re van olyan ℜ, hogy Aut(ℜ) = ⟨G_{R}, φ^{−1}G_{R}φ⟩. Viszafelé triviális. ■

2.25 TÉTEL. Z_{p} globálisan CI-csoport.

Bizonyítás. Minden δ ∈ Sym(Z_{p})-re (Z_{p})_{R} és (Z_{p})_{R}^{δ} p-Sylow részcsoportok ⟨(Z_{p})_{R}, (Z_{p})_{R}^{δ}⟩- ben, Sylow II. tétele szerint konjugáltak, azaz (Z_{p})_{R} pronormális, tehát az előző állításból következik a tétel. ■

2.26 ÁLLÍTÁS. (D)CI-csoport minden részcsoportja is (D)CI-csoport.

Bizonyítás. Legyen G egy (D)CI-csoport, H ≤ G, S, T ⊆ H és teljesüljön: Cay(H, S) ≅ Cay(H, T). Feltehető, hogy a gráf összefüggő, azaz ⟨S⟩ = ⟨T ⟩ = H, mert különben vesszük a komplementert. Láttuk, hogy ekkor Cay(G, S) ≅ Cay(G, T), tehát létezik α ∈ AutG, melyre S^{α} = T. Végül H^{α} = ⟨S^{α}⟩ = ⟨T ⟩ = H, tehát α|_{H} ∈ AutH. ■

(D)CI-csoportok

3.1. Ciklikus gráfok

3.1 DEFINÍCIÓ. Legyenek 0 < k_{1} < k_{2} < ⋯ < k_{m} < n egész számok és képezzük azt a G_{n}(k_{1}, …, k_{m}) irányított gráfot a P_{1}, …, P_{n} csúcsok halmazán, ahol P_{i}-ből P_{j}-be pontosan akkor vezet él, ha valamely t-re k_{t} ≡ j − i (mod n). Az ilyen gráfot ciklikus gráfnak nevezzük.

A ciklikus gráfban a csúcsok P_{i} ↦ P_{i+k} permutációi (ahol az indexeket modulo n kell tekinteni, valamint k = 0, …, n − 1) mind automorfizmusai a gráfnak. Két ilyen gráf, G_{n}(k_{1}, …, k_{m}) és G_{n}(k′_{1}, …, k′_{m}) izomorfiájához elegséges feltétel egy olyan r szám valamint az 1, …, m halmaz egy α permutációjának létezése, amelyekre 0 < r < n, r relatív prím n-hez és k′_{t} ≡ rk_{α(t)} (mod n) minden t-re (1 ≤ t ≤ m). Ádám András [1] azt sejtette, hogy ez a feltétel szükséges is, az az minden ciklikus csoport DCI-csoport.

Foglalkozzunk előszőr az irányítatlan esetettel. Néhány kis szám kivételével valamennyi négyzetszámra adott ellenpéldát Babai László és Frankl Péter [5]:

3.2 LEMMA. Z_{n^{2}} nem CI-csoport, ha n = 5 vagy n ≥ 7.

Bizonyítás. Mivel n ≥ 5 és n ≠ 6, ezért φ(n) > 2, ahol φ az Euler függvény. Igy létezik egy n-hez relatív prim s, hogy 2 ≤ s ≤ n − 2. Tekintsük Z_{n^{2}} következő részhalmazait:

A = {n, −n}; B = {kn + 1, kn − 1 : k = 0, …, n − 1}
H = A ∪ B; K = sA ∪ B = {sn, −sn} ∪ B

Világos, hogy minden S ⊆ Z_{n}, S = −S esetén Cay(Z_{n^{2}}, nS ∪ B) ≅ C_{n}[Cay(Z_{n}, S)], ahol C_{n} egy n hosszú irányítatlan kör. A mi esetünkben

Cay(Z_{n}, {1, −1}) ≅ Cay(Z_{n}, {s, −s}) ≅ C_{n}

tehát

Cay(Z_{n^{2}}, H) ≅ Cay(Z_{n^{2}}, K) ≅ C_{n}[C_{n}]

Ezzel szemben nem létezik olyan d, hogy dH = K, (d, n^{2}) = 1. Ebből ugyanis dA = sA, dB = B (mod n^{2}), majd d ≡ ±s mod n következne, ami ellentmond annak, hogy B minden eleme kongruens ±1 (mod n). ■

Késöbb Pálfy Péter Pál [23] újabb eseteket zárt ki.

3.3 LEMMA. Z_{8m} nem CI-csoport, ha m > 1.

Bizonyítás. Legyenek T_{1} = {±2, ±(2m + 1), ±(2m − 1)} és T_{2} = {±2, ±1, ±(4m − 1)} a csatlakozó halmazok. Könnyen látható, hogy az

x ↦ \{ \begin{matrix}x, & ha x páros \\ x + 2m, & ha x páratlan \end{matrix}

permutáció egy gráfizomorfizmus Cay(Z_{8m}, T_{1}) és Cay(Z_{8m}, T_{2}) között, de nincs olyan k, melyre (k, 8m) = 1 és az x ↦ kx csoportautomorfizmus T_{1}-et T_{2}-be vinné. ■

3.4 LEMMA. Z_{9m} nem CI-csoport, ha m > 2.

Bizonyítás. Tekintsük a T_{i} = {±1, ±(3m + 1), ±(6m + 1), ±3(im + 1)}, i = 0, 1, 2 csatlakozó halmazokkal megadott Cayley-gráfokat és a következő φ(i) permutációkat:

x ↦ \{ \begin{matrix}(im + 1)x, & ha x ≡ 0(mod 3) \\ (im + 1)x − im, & ha x ≡ 1(mod 3) \\ (im + 1)x − 2im, & ha x ≡ 2(mod 3) \end{matrix}

Ha im+1 nem osztható 3-mal, akkor φ(i) izomorfizmus Cay(Z_{9m}, T_{0})-ból Cay(Z_{9m}, T_{i})-be. Ha kT_{0} = T_{i}, akkor k = ±(3jm + 1), 0 ≤ j ≤ 2, és ±3(im + 1) = k(±3) = ±3(3jm + 1) = ±3. Ha 3(im + 1) = 3, akkor i = 0. Ha pedig 3(im + 1) = −3, akkor 3im ≡ −6(mod 9m), 3m osztja a 6-ot, ami m > 2 miatt lehetetlen. Mivel m+1, vagy 2m+1 nem osztható 3-mal, ezért Cay(Z_{9m}, T_{0}) és Cay(Z_{9m}, T_{i}) (i = 1 vagy 2) szolgáltatják a szükséges ellenpéldát. ■

3.5 TÉTEL. Ha Z_{n} CI-csoport, akkor

n ∈ {8, 9, 18} vagy n = k, 2k vagy 4k,

ahol k páratlan négyzetmentes szám.

Bizonyítás. Legyen G = Z_{n} CI-csoport. A 2.26 állítás szerint CI-csoport minden részcsoportja CI, ezért az előző három lemmából következik, hogy G p-Sylow részcsoportja csak Z_{p}, Z_{4}, Z_{8} vagy Z_{9} lehet.Ha az utóbbi két eset valamelyike fennáll, akkor az utolsó két lemmából n = 8, 9 vagy 18. Ha nem, akkor n = k, 2k vagy 4k, ahol k páratlan négyzetmentes szám. ■

Irányított gráfokkal az n = 8, 9, 18 esetekben is adható ellenpélda. Már a vizsgálatok legelején B. Elspas és J. Turner [3] megmutatták, hogy 8 csúcsra az a két ciklikus gráf, amelyre P_{8} szomszédai P_{1}, P_{2} és P_{5}, illetve amelyikre P_{1}, P_{5} és P_{6} egymással izomorfak (egy izomorfizmus például a P_{2i} → P_{10−2i}, P_{2i−1} → P_{9−2i} (i = 1, 2, 3, 4) leképezés), de nincs olyan r, amellyel r{1, 2, 5} ≡ {1, 5, 6} (mod 8). Az irányított esetben tehát a következő adódik.

3.6 TÉTEL. Ha Z_{n} DCI-csoport, akkor

n = k, 2k vagy 4k,

ahol k páratlan négyzetmentes szám.

3.2. Általános eset

Babai László és Frankl Péter [5] vették észre a CI csoportok alábbi fontos tulajdonságát.

3.7 LEMMA. Legyen G egy véges (D)CI-csoport,

U_{1} ≤ ⋯ ≤ U_{n} = G , V_{1} ≤ ⋯ ≤ V_{n} = G , |U_{i}| = |V_{i}| (i = 1, … n).

Ekkor létezik α ∈ Aut(G), hogy

α(U_{i}) = (V_{i}) (i = 1, … n).

Bizonyítás. Legyenek S_{0} = T_{0} = U_{0} = T_{0} = {0},

n_{i} := |U_{i}/U_{i−1}| = |V_{i}/V_{i−1}|, S_{i} := U_{i} \ S_{i−1}, T_{i} := V_{i} \ T_{i−1} (i = 1, …, n)

Ekkor Cay(U_{1}, S_{1}) ≅ Cay(V_{1}, T_{1}) ≅ K_{n_{1}}, Cay(U_{i+1}, S_{i+1}) izomorf Cay(U_{i}, S_{i}) komplementerének n_{i+1} darab példányával és ugyanez elmondható U és S helyett V -vel és T -vel. Ezért Cay(U_{i}, S_{i}) ≅ Cay(V_{i}, T_{i}) (i = 1, …, n), Cay(G, S_{n}) ≅ Cay(G, T_{n}) G egy (D)CIcsoport, így létezik α ∈ Aut(G), hogy S_{n}^{α} = T_{n}. Tegyük fel, hogy S_{n−k}^{α} = T_{n−k} valamilyen 0 ≤ k ≤ n − 1. Ekkor U_{n−k}^{α} = ⟨S_{n−k}^{α}⟩ = ⟨T_{n−k}^{α}⟩ = V_{n−k} és S_{n−k−1}^{α} = (U_{n−k} \ S_{n−k} \ {0})^{α} = = (V_{n−k} \ T_{n−k} \ {0}) = T_{n−k−1}. Teljes indukcióval α(U_{i}) = (V_{i}) (i = 1, … n). ■

3.8 DEFINÍCIÓ. Legyen M egy Abel csoport, melynek minden Sylow részcsoportja elemi Abel, n ∈ {2, 3, 4, 8, 9} pedig olyan, hogy (|M|, n) = 1. Ekkor

E(M, n) := M⟨z⟩, ahol o(z) = n és minden x ∈ M-re :

x^{z} := \{ \begin{matrix}x^{−1}, & ha n = 2, 4 vagy 8 \\ x^{l}, & ha n = 3 vagy 9, és itt l^{3} ≡ 1 (mod exp(M)), (l(l − 1), exp(M)) = 1 \end{matrix}

Cai Heng Li és Pálfy Péter Pál készülő cikkéből kiderül, hogy jelenleg mely csoportok lehetnek CI-csoportok:

3.9 TÉTEL. Legyen G egy véges CI-csoport.

(a) Ha G nem tartalmaz 8- vagy 9-rendű elemet, akkor G = H_{1} × H_{2} × H_{3}, ahol a tényezők rendjei páronként relatív primek és

H_{1} Abel és minden Sylow részcsoportja elemi Abel vagy Z_{4}; H_{2} a következő csoportok valamelyike: E(M, 2), E(M, 4), Q vagy 1; H_{3} pedig a következőké: E(M, 3), A_{4} vagy 1.

(b) Ha G tartalmaz 8-rendű elemet, akkor G ≅ E(M, 8) vagy Z_{8}.

(c) Ha G tartalmaz 9-rendű elemet, akkor G egy a következő csoportok közül: Z_{9} >◁Z_{2}, Z_{9} >◁Z_{4}, Z_{2}^{2} >◁Z_{9}, vagy Z_{9} × Z_{2}^{n}, ahol n ≤ 5.

Li, Praeger és Xu [14] pedig az irányított esetben adták meg a legjobb eredményt:

3.10 TÉTEL. Legyen G egy véges DCI-csoport. Ekkor G minden Sylow részcsoportja elemi Abel, Z_{4} vagy Q, valamint G = U × V, ahol (|U|, |V |) = 1, U Abel és V = 1, Q, A_{4}, E(M, 2) vagy E(M, 2).

Az elemi Abel csoportok esete

4.1. G-invariáns partíciók

Az alábbiakban mindig

G = Z_{p}^{n} és Γ = Cay(Z_{p}^{n}, S)

4.1 LEMMA. Legyen G_{R}^{δ} ≤ AutΓ (δ ∈ Sym(G)). Ekkor léteznek P ∈ Syl_{P} (AutΓ) és γ ∈ AutΓ, hogy

⟨G_{R}, G_{R}^{γδ}⟩ ≤ P

Bizonyítás. A Sylow tételek miatt nyilvánvaló. ■

Ismét a Sylow tételeket alkalmazva P ≤ P^{∗} ∈ Syl_{P} (Sym(G)), ahol P^{∗} ≅ \underbrace{Z_{p} ≀ Z_{p} ≀ ⋯ ≀ Z_{p}}_{n}

meghatároz P^{∗}-invariáns partíciók egy B = {B_{i}|i = 1, …, n + 1} rendszerét:

B_{i} = {(B_{i})p : p ∈ P^{∗}}, {0} = B_{1} < ⋯ < B_{n} < B_{n+1} = G, és B_{i} M_{i}-partíció.

B_{i+1} = ⟨g_{1}, …, g_{i}⟩, τ_{i} := (g_{i})_{R}, T_{i} := ⟨τ_{1}⟩ ≀ ⋯ ≀ ⟨τ_{i}⟩ ≀ Sym(B_{i+1}) ≤ M_{i+1}, T_{n} = P^{∗}.

G_{R} ≤ P ≤ P^{∗} ⇒ B_{i} = {(B_{i})p : p ∈ P } = {(B_{i})τ : τ ∈ ⟨τ_{i}, … τ_{n}⟩}

4.2 DEFINÍCIÓ. Minden 1 ≤ i ≤ n-re jelölje ι_{i} a következő M_{i} → Sym(B_{i}) homomorfizmust:

(g + B_{i})(ι_{i}(m)) = (g + B_{i})m (g ∈ G, m ∈ M_{i})

Ekkor ι_{i}(P^{∗}) ∈ Syl_{P} (Sym(B_{i})) a {B_{j}|j = i, …, n} rendszert határozza meg, ezért

ι_{i}((B_{i+1})_{R}) = Z(ι_{i}(P^{∗})) ≤ Z(ι_{i}(P)).

4.3 LEMMA. Legyen ⟨G_{R}, G_{R}^{δ}⟩ ≤ P ∈ Syl_{p}(AutΓ) (δ ∈ Sym(G)). Ekkor minden 1 ≤ i ≤ n-re létezik υ_{i} ∈ G_{R}^{δ}, hogy

ι_{i}(τ_{i}) = ι_{i}(υ_{i}), speciálisan τ_{1} = υ_{1}.

Bizonyítás. Az előzőek szerint ι_{i}(τ_{i}) ∈ Z(ι_{i}(P)), ι_{i}(G_{R}^{δ}) tranzitív és Abel, következésképp ⟨ι_{i}(τ_{i}), ι_{i}(G_{R}^{δ})⟩ is tranzitív és Abel. Tehát mindkettő reguláris, igy ι_{i}(τ_{i}) ∈ ι_{i}(G_{R}^{δ}). Végül B_{1} = G miatt ι_{1} = id_{P}. ■

4.4 KÖVETKEZMÉNY. Z_{p} DCI-csoport

Bizonyítás. Legyen Γ = Cay(Z_{p}, S) és (Z_{p})_{R}^{δ} ≤ AutΓ. Az előző két lemma szerint τ_{1} = υ_{1}, (Z_{p})_{R} = (Z_{p})_{R}^{γδ} (γ ∈ AutΓ), a Babai lemmából pedig Γ CI-gráf. ■

4.5 KÖVETKEZMÉNY. Legyen ⟨G_{R}, G_{R}^{δ}⟩ ≤ P ∈ Syl_{p}(AutΓ) (δ ∈ Sym(G)). Ekkor létezik α ∈ Aut(G), hogy δα ∈ P^{∗}.

Bizonyítás. Teljes indukcióval belátjuk, hogy léteznek α_{1}, …, α_{n} ∈ Aut(G), hogy minden 1 ≤ i ≤ n-re δα_{1} … α_{i} ∈ T_{i}. A lemma szerinti υ_{1} ∈ G_{R}^{δ}-hez létezik w_{1} ∈ G és α_{1} ∈ Aut(G), hogy δ(w_{1})_{R}δ^{−1} = υ_{1} és (w_{1})α_{1} = g_{1}. Legyen δ_{1} := δα_{1}.

δ_{1}(g_{1})_{R}δ_{1}^{−1} = δα_{1}(g_{1})_{R}α_{1}^{−1}δ^{−1} = δ(w_{1})_{R}δ^{−1} = υ_{1} = τ_{1} = (g_{1})_{R}

(δ_{1}^{−1}(0) δ_{1}^{−1}(g_{1}) … δ_{1}^{−1}((p − 1)g_{1})) … = (0 g_{1} … (p − 1)g_{1}) …

Ebből δ_{1} ∈ T_{1}, tehát i = 1-re igaz. Most tegyük fel, hogy minden 1 ≤ i ≤ k(< n))-re már találtunk megfelelő α_{i}-t, és a δ_{i} := δα_{1} … α_{i} jelöléssel δ_{i} ∈ T_{i} ≤ M_{i+1}. Mivel (B_{k+1})_{R} ≤ ker(ι_{k+1}) ◁ M_{i+1}, υ_{k+1} ∉ ker(ι_{k+1}), ezért w ∈ (B_{k+1}) esetén ι_{k+1}(δ_{k}w_{R}δ_{k}^{−1}) ≠ ι_{k+1}(υ_{k+1}), tehát léteznek w_{k+1} ∈ G \ B_{k+1} és α_{k+1} ∈ Aut(G):

δ_{k}(w_{k+1})_{R}δ_{k}^{−1} = υ_{k+1}, (w_{k+1})α_{k+1} = g_{k+1}, (g_{i})α_{k+1} = g_{i} (i = 1, …, k).

Innen δ_{k+1} := δ_{k}α_{k+1} ∈ M_{k+1} és

ι_{k+1}(δ_{k+1})ι_{k+1}((g_{k+1})_{R})ι_{k+1}(δ_{k+1}^{−1}) = ι_{k+1}(δ_{k+1}g_{k+1}δ_{k+1}^{−1}) = ι_{k+1}(δ_{k}w_{k+1}δ_{k}^{−1}) =

= ι_{k+1}(υ_{k+1}) = ι_{k+1}(τ_{k+1}) = ι_{k+1}((g_{k+1})_{R})

(ι_{k+1}(δ_{k+1})^{−1}(B_{k+1}) ι_{k+1}(δ_{k+1})^{−1}(g_{k+1} + B_{k+1}) …

… ι_{k+1}(δ_{k+1})^{−1}((p − 1)g_{k+1} + B_{k+1})) …

= (B_{k+1} (g_{k+1} + B_{k+1}) … ((p − 1)g_{k+1} + B_{k+1})) …

azaz ι_{k+1}(δ_{k+1}) ∈ ι_{k+1}(T_{k+1}) = ι_{k+1}(⟨τ_{k+1}⟩) ≀ Sym(B_{k+2}). Viszont δ_{k+1} = δ_{k}α_{k+1} ∈ T_{k}, ezért δ_{k+1} ∈ T_{k+1}, és ezzel minden 1 ≤ i ≤ n-re beláttuk, hogy δ_{i} ∈ T_{i}. Az α := α_{1} … α_{n} jelöléssel pedig kapjuk:

δα = δ_{n} ∈ T_{n} = P^{∗}.
■

4.6 ÁLLÍTÁS. Legyen G_{R}^{δ} ≤ AutΓ (δ ∈ Sym(G)). Ekkor

(1) léteznek γ ∈ AutΓ és α ∈ Aut(G), hogy a δ′ := γδα jelöléssel

⟨G_{R}, G_{R}^{δ′}⟩ ≤ P ≤ P^{∗}, és G_{R}^{δ′} = G_{R}^{γδ}

ahol P ∈ Syl_{p}(AutΓ) és δ′ ∈ P^{∗} ∈ Syl_{p}(Sym(G)), valamint

(2) minden 1 ≤ i ≤ n-re létezik υ_{i} ∈ G_{R}^{δ′}, hogy

τ_{1} = υ_{1}, ι_{i}(τ_{i}) = ι_{i}(υ_{i}), és (B_{i+1})_{R}^{δ′} = ⟨υ_{1}, … υ_{i}⟩

Bizonyítás. Az eddigieket felhasználva csak (2) második fele szorul bizonyításra. Mivel N_{i} := kerι_{i+1} ∩ P^{∗} ◁ P^{∗}, δ′ ∈ P^{∗}, és (B_{i+1})_{R} = G_{R} ∩ N_{i}, ezért (B_{i+1})_{R}^{δ′} = G_{R}^{δ′} ∩ N_{i}. Végűl minden j ≤ i-re ι_{j}(υ_{j}) = ι_{j}(τ_{j}) és τ_{j} ∈ N_{j} \ N_{j−1} miatt υ_{j}τ_{j}^{−1} ∈ N_{j−1} ≤ N_{j} és υ_{j} ∈ N_{j} \ N_{j−1}. Tehát G_{R}^{δ′} ∩ N_{i} = ⟨υ_{1}, … υ_{i}⟩ és kész. ■

4.2. Koszorú reláció

A B_{i} partíció elemei között értelmezhető a következő, koszorú reláció:

B_{i} + a_{1} ∼ B_{i} + a_{2} ⟺ {(b′′ + a_{t}) − (b′ + a_{l}) ∈ S ⇒ (B_{i} + a_{t}) − (b′ + a_{l}) ⊆ S }

Ennek segítségével kapjuk az i-dik Cayley segédgráfot:

Γ_{i} = (B_{i}, E), E := \{(B_{i} + x, B_{i} + y)|B_{i} + x ≁ B_{i} + y\}, \overline{Γ_{i}} = Γ komplementergráfja

Nyílván B_{i} + x ∼ B_{i} + y pontosan azt jelenti, hogy

{y − x + B_{i} ∈ S vagy y − x + B_{i} ∈ G \ S} és {x − y + B_{i} ∈ S vagy x − y + B_{i} ∈ G \ S}

Az elöbbiek tömör általánosítása a következő 4.7 DEFINÍCIÓ. Legyenek H ⊆ G, Ξ_{H} : G ⟶ Z_{2} és S : P(G) ⟶ P(G) :

Ξ_{H}(g) := \{ \begin{matrix}1, & ha g + H ⊆ S vagy g + H ⊆ G \ S \\ 0, & különben \end{matrix}

S(H) := {g ∈ G|Ξ_{H}(g) = 0 vagy Ξ_{H}(g^{−1}) = 0}, S_{i} := S(B_{i}) (i = 1, …, n)

\overline{S(H)} := G \ S(H) = \{g ∈ G|Ξ_{H}(g) = Ξ_{H}(g^{−1}) = 1\}.

H_{1} ⊆ H_{2} esetén S(H_{1}) ⊆ S(H_{2}), tehát

Ø = S_{1} ⊆ S_{2} ⊆ ⋯ ⊆ S_{n} és G = \overline{S_{1}} ⊇ \overline{S_{2}} ⊇ ⋯ ⊇ \overline{S_{n}}

Ezzel B_{i} + x ∼ B_{i} + y pontosan azt jelenti, hogy y − x ∈ S_{i}, továbbá Γ_{i} = (B_{i}, S_{i} + B_{i}) és \overline{Γ_{i}} = (B_{i}, \overline{S_{i}} + B_{i}).

4.8 LEMMA. Legyenek H_{1}, H_{2} ⊆ H ⊆ G, ahol H + H_{1} = H + H_{2} = H. Ekkor

g + H ⊆ \overline{S(H_{1})} ∩ \overline{S(H_{2})} ⇒ g + H ⊆ \overline{S(H_{1} + H_{2})}.

Bizonyítás. Tegyük fel, hogy g + h + h_{1} + h_{2} ∈ S (g ∈ G, h ∈ H, h_{1} ∈ H_{1}, h_{2} ∈ H_{2}). Mivel h + h_{1} ∈ H, Ξ_{H_{2}}(g + h + h_{1}) = 1, ezért g + h + h_{1} + h′_{2} ∈ S minden h′_{2} ∈ H_{2}-re. Tovább h + h′_{2} ∈ H, Ξ_{H_{1}}(g + h + h′_{2}) = 1, tehát g + h + h′_{1} + h′_{2} ∈ S minden h′_{1} ∈ H_{1} és h′_{2} ∈ H_{2}-re. Másszóval Ξ_{H_{1}+H_{2}}(g + h) = 1. Hasonlóan Ξ_{H_{1}+H_{2}}(−g − h) = 1, vagyis g + h ∈ \overline{S(H_{1} + H_{2})} minden h ∈ H-ra. ■

4.3. Cayley segédgráfok

4.9 DEFINÍCIÓ. Legyen H ≤ G. Ekkor Cay(G/H, S(H) + H)-t nevezzük a Cay(G, S) Cayley gráf H szerinti Cayley segédgráfjának és jelöljük Γ(H)-val, a komplementerét pedig \overline{Γ(H)}-sal.

Tegyük fel, hogy τ_{i} = υ_{i}, (i = 1, …, k − 1(< n)), legyenek υ ∈ G_{R}^{δ} és a ∈ G képe a G → G/B_{k} természetes homomorfizmusnál \overline{a}. Ekkor minden b ∈ B_{k}-ra [b_{R}, υ] = [b_{R}, τ] = 1,

(a + b)υ − (a + b)τ = (a)υ + b − ((a)τ + b) = (a)υ − (a)τ (τ ∈ G_{R}).

4.10 DEFINÍCIÓ. (\overline{a}, υ, τ) := (a)υ − (a)τ

4.11 Megjegyzés. (a + b)υτ^{−1} = ((a + b)τ + (a, υ))τ^{−1} = a + b + (\overline{a}, υ, τ)

(a + b)υ = (a)τ + b + (\overline{a}, υ, τ)
(\overline{a}, υ′υ′′, τ′τ′′) = (a)υ′υ′′ − (a)τ′τ′′ = ((a)τ′ + (\overline{a}, υ′, τ′))υ′′ − (a)τ′τ′′ =
= (\overline{a}, υ′, τ′) + ((\overline{a})(ι_{k}(τ′)), υ′′, τ′′).

4.12 LEMMA. Legyen g := y − x, valamint (\overline{x}, υ, τ), (\overline{y}, υ, τ) ∈ B_{k}. Ekkor

g + B_{k} ⊆ \overline{S(⟨g^{∗∗}⟩)}, ahol g^{∗∗} := (\overline{y}, υ, τ) − (\overline{x}, υ, τ) ∈ B_{k}.

Bizonyítás. Ha g^{∗∗} = 0, akkor \overline{S(0)} = G miatt trivialitás. Legyen b ∈ B_{k} tetszőleges, g^{∗∗} ≠ 0 és tegyük fel, hogy g +b+rg^{∗∗} ∈ S valamilyen r ∈ F_{p}-vel. Ekkor minden r′ ∈ F_{p}-re

(y + b + rg^{∗∗})(υτ^{−1})^{r′} − (x)(υτ^{−1})^{r′} = y + b + rg^{∗∗} + r′(\overline{y}, υ, τ) − x − r′(\overline{x}, υ, τ) =

= g + b + (r + r′)g^{∗∗} ∈ S.

Ebből Ξ_{⟨g^{∗∗}⟩}(g + b) = 1 és ugyan így Ξ_{⟨g^{∗∗}⟩}(−g − b) = 1, azaz (g + b) ∈ \overline{S(⟨g^{∗∗}⟩)}. ■

4.13 LEMMA. Legyenek \{(\overline{x}, ϕ_{i}, φ_{i}), (\overline{y_{i}}, ϕ_{i}, φ_{i}), y_{i} − (x)ϕ_{j} | i, j ∈ \{1, 2\}, i ≠ j\} ⊆ B_{k}, h_{i} =: y_{i} − x és h_{i}^{∗∗} := (\overline{y_{i}}, ϕ_{i}, φ_{i}) − (\overline{x}, ϕ_{i}, φ_{i}) ∈ B_{k}. Ekkor

h_{i} + B_{k} ⊆ \overline{S(⟨h_{j}^{∗∗}⟩)}.

Bizonyítás. Előszőr (\overline{x}, ϕ_{1}ϕ_{2}, φ_{1}φ_{2}) = (\overline{x}, ϕ_{2}ϕ_{1}, φ_{2}φ_{1}), így

(\overline{x}, ϕ_{1}, φ_{1}) + ((\overline{x})(ι_{k}(φ_{1})), ϕ_{2}, φ_{2}) = (\overline{x}, ϕ_{2}, φ_{2}) + ((\overline{x})(ι_{k}(φ_{2})), ϕ_{1}, φ_{1}).

(\overline{x})(ι_{k}(φ_{i})) = (\overline{x})(ι_{k}(ϕ_{i})) = \overline{y_{j}}. (i, j ∈ \{1, 2\}, i ≠ j)

h_{1}^{∗∗} := (\overline{y_{1}}, ϕ_{1}, φ_{1}) − (\overline{x}, ϕ_{1}, φ_{1}) = (\overline{y_{2}}, ϕ_{2}, φ_{2}) − (\overline{x}, ϕ_{2}, φ_{2}) = h_{2}^{∗∗},

majd a 4.12 lemmát alkalmazva

h_{i} + B_{k} ⊆ \overline{S(⟨h_{i}^{∗∗}⟩)} = \overline{S(⟨h_{j}^{∗∗}⟩)}
■

4.14 DEFINÍCIÓ. Legyenek

a^{∗} := (\overline{a}, υ_{k}, τ_{k}), és B_{k}(g) := ⟨y^{∗} − x^{∗}| y − x = g⟩ (a, g ∈ G).

vagy, ha félreértésre nem ad okot, B(g) := B_{k}(g).

4.15 LEMMA. B(rg + th) ≤ B(g) + B(h), B(rg) = B(g) (r, t = 1, …, p − 1)

Bizonyítás. y^{∗} − x^{∗} ∈ B(g + h), y − x = g + h,

y^{∗} − x^{∗} = ((g + h + x)^{∗} − (h + x)^{∗}) + ((h + x)^{∗} − x^{∗}) ∈ B(g) + B(h),

B(rg) ≤ rB(g) = B(g), B(g) = B(r′rg) ≤ r′B(rg) = B(rg) (r = 1, …, p − 1),

B(rg + th) ≤ B(rg) + B(th) = B(g) + B(h)
■

4.16 LEMMA. rg + B_{k} ⊆ \overline{S(B(g))}, (r = 1, …, p − 1)

Bizonyítás. Legyen g = y−x. Ekkor x^{∗}, y^{∗} ∈ B_{k}, és a 4.12 lemmából g+B_{k} ⊆ \overline{S(⟨y^{∗} − x^{∗}⟩}. Tehát

g + B_{k} ⊆ ⋂_{y−x=g} \overline{S(⟨y^{∗} − x^{∗}⟩)}

majd a 4.8 lemmából

g + B_{k} ⊆ \overline{S( ∑_{y−x=g}⟨y^{∗} − x^{∗}⟩)} = \overline{S((B(g))}.

Ezt g helyett rg-vel is mondhatjuk, B(rg) = B(g) és készen vagyunk. ■

4.4. A segédgráfok módszere

A segédgráfok módszere abból áll, hogy ha a bizonyítás során olyan esetbe ütközünk, amelyet nem tudunk megoldani, mert túl bonyolult vagy túl sok alesetre bomlana szét, akkor alkalmasan választott segédgráfok segítségével vagy megmutatjuk, hogy ez igazából olyan eset amelyet már elintéztünk, vagy az aleseteket ügyesen partícionálva, az egyes osztályokat visszavezetjük már megoldott esetekre.

4.17 DEFINÍCIÓ. Legyen (·, ·) : G × G → F_{p} szimmetrikus bilineáris függvény, melyre (g_{k}, g_{k}) = 1 és (g_{k}, g_{j}) = 0, ha j < k. Ekkor π_{k} ∈ Sym(G) legyen a következő:

(x)π_{k} := (x)τ_{k}^{−(x,g_{k})}υ_{k}^{(x,g_{k})} (x ∈ G)

4.18 LEMMA.

(1) υ_{k}^{π_{k}} = τ_{k}, π_{k} ∈ C_{Sym(G)}((B_{k})_{R})

(2) y − x ∈ g_{k}^{⊥} ∩ S ⇒ (y)π_{k} − (x)π_{k} ∈ S

(3) (y)π_{k} − (x)π_{k} = y − x + ∑_{i=1}^{(y,g)}(y − ig)^{∗} − ∑_{i=1}^{(x,g)}(x − ig)^{∗} ∈ y − x + B_{k} (x, y ∈ G)

(4) y − x ∈ S ∩ \overline{S_{k}} ⇒ (y)π_{k} − (x)π_{k} ∈ S Bizonyítás.

(1) Mivel (x, g_{k}) + 1 = (x + g_{k}, g_{k}), így minden x ∈ G-re (x)π_{k}υ_{k}π_{k}^{−1} = (x)τ_{k}^{−(x,g_{k})}υ_{k}^{(x,g_{k})}υ_{k}π_{k}^{−1} = (x)τ_{k}τ_{k}^{−((x,g_{k})+1)}υ_{k}^{(x,g_{k})+1}π_{k}^{−1} =

= (x + g_{k})τ_{k}^{−(x+g_{k},g_{k})}υ_{k}^{(x+g_{k},g_{k})}π_{k}^{−1} = (x + g_{k})π_{k}π_{k}^{−1} = (x)τ_{k},

minden b ∈ B_{k}-ra [b_{R}, υ] = [b_{R}, τ] = 1 és (x + b, g_{k}) = (x, g_{k}), ezért minden x, y ∈ Gre (x)b_{R}π_{k} = (x + b)τ_{k}^{−(x+b,g_{k})}υ_{k}^{(x+b,g_{k})} = (x)b_{R}τ_{k}^{−(x,g_{k})}υ_{k}^{(x,g_{k})} = (x)τ_{k}^{−(x,g_{k})}υ_{k}^{(x,g_{k})}b_{R} = (x)π_{k}b_{R}

(2) y − x ∈ S, (x, g_{k}) = (y, g_{k}) =: i, így (y)π − (x)π = (y)τ_{k}^{i}υ_{k}^{i} − (x)τ_{k}^{i}υ_{k}^{i} ∈ S (3)

(y)π_{k} − (x)π_{k} = (y)τ_{k}^{−(y,g)}υ_{k}^{(y,g)} − (x)τ_{k}^{−(x,g)}υ_{k}^{(x,g)} =

= (y − (y, g)g_{k})((υ_{k}τ_{k}^{−1})τ)^{(y,g)} − (x − (x, g)g_{k})((υ_{k}τ_{k}^{−1})τ)^{(x,g)} =

= y − x + ∑_{i=1}^{(y,g)}(y − ig)^{∗} − ∑_{i=1}^{(x,g)}(x − ig)^{∗} ∈ y − x + B_{k}.

(4) \overline{S_{k}} definíciójából és az előző pontból

(y)π_{k} − (x)π_{k} ∈ y − x + B_{k} ⊆ S

■

4.19 LEMMA. Tegyük fel, hogy g_{k} ∉ ⟨S_{k}⟩ < G. Ekkor alkalmas (·, ·)-el π_{k} ∈ Aut(Γ). Bizonyítás. Válasszuk (·, ·)-t úgy, hogy g_{k} ∈ S_{k}^{⊥} is teljesüljön. Ha y − x ∉ g_{k}^{⊥}, akkor y − x ∉ S_{k} vagyis y − x ∈ \overline{S_{k}}. Tehát az előző lemma szerint y − x ∈ S (x, y ∈ G) esetén (y)π_{k} − (x)π_{k} ∈ S. ■

4.20 KÖVETKEZMÉNY. Z_{p}^{2} DCI-csoport Bizonyítás. Legyen G = Z_{p}^{2}, Γ = Cay(G, S) és G_{R}^{δ} ≤ AutΓ. A 4.1 és 4.3 lemmák szerint υ_{1} = τ_{1} ∈ G_{R}. Ha B(g_{2}) = {0}, akkor minden x ∈ G-re x^{∗} =: b ∈ B_{2}, (x)υ_{2}τ_{2}^{−1} = (x)b_{R}, és υ_{2} = τ_{2}b_{R} ∈ G_{R}. Ha B(g_{2}) ≠ \{0\}, akkor B(g_{2}) = B_{2}, a 4.16 lemmából rg_{2} + B_{2} ⊆ \overline{S_{2}} (r = 1, …, p − 1), ebből g_{2} ∉ ⟨S_{2}⟩, és az előző két lemmából π_{2} ∈ C_{Aut(Γ)}(τ_{1}), υ_{2}^{π_{2}} = τ_{2}. Végül a Babai lemmát alkalmazva Γ CI-gráf. ■

4.21 LEMMA. Legyenek G = Z_{p}^{2}, Γ = Cay(G, S), ⟨G_{R}, G_{R}^{δ}⟩ ≤ P ∈ Syl_{p}(AutΓ). Ekkor

G_{R} = G_{R}^{δ} vagy rg_{2} ∈ \overline{S_{2}} (r = 1, …, p − 1)

Bizonyítás. Az iménti következmény bizonyításából nyilvánvaló. ■

4.22 DEFINÍCIÓ. Legyen B_{k+1} ≤ H ≤ G.

B_{k}(H) := ∑_{h∈H} B_{k}(h)

4.23 LEMMA. rg_{k} + B_{k} ⊆ \overline{S(B_{k}(H))}.

Bizonyítás. Legyen y−x = h ∈ H \B_{k+1}. A regularitás miatt léteznek τ ∈ G_{R} és υ ∈ G_{R}^{δ}, hogy (\overline{x})ι_{k}(υ) = (\overline{x})ι_{k}(τ) = \overline{y}. A 4.13 lemma feltételei az y_{1} = y, y_{2} = x+g_{k}, ϕ_{1} = υ_{k}, ϕ_{2} = υ szereposztás mellett definíció szerint teljesülnek, tehát

g_{k} + B_{k} ⊆ \overline{S(⟨y^{∗} − x^{∗}⟩)}.

Ha y − x ∈ B_{k+1}, akkor ugyanez a 4.16 lemmából következik, tehát a 4.8 lemmát kétszer alkalmazva

g_{k} + B_{k} ⊆ \overline{S( ∑_{y−x=h}⟨y^{∗} − x^{∗}⟩)} = \overline{S(B_{k}(h))} és g_{k} + B_{k} ⊆ \overline{S(∑_{h∈H} B_{k}(h))} = \overline{S(B_{k}(H))}.

Vegyünk υ helyett υ^{r}-t (r ≠ 0) és az előzővel analóg módon, a B_{k}(H)-nak megfelelő alteret B_{k}(H, r)-el jelölve:

rg_{k} + B_{k} ⊆ \overline{S(B_{k}(H, r))},

B_{k}(H, r) = ∑_{h∈H} ∑_{y−x=h} ⟨ ∑_{t=0}^{r−1}(y + tg_{k})^{∗} − ∑_{t=0}^{r−1}(x + tg_{k})^{∗}⟩ ≤

≤ ∑_{h∈H} ∑_{y−x=h} ∑_{t=0}^{r−1} ⟨(y + tg_{k})^{∗} − (x + tg_{k})^{∗}⟩ ≤ ∑_{h∈H} B_{k}(h) = B_{k}(H),

alkalmas t ∈ F_{p}-vel rt = 1 és B_{k}(H) = B_{k}(H, rt) ≤ B_{k}(H, r) ≤ B_{k}(H), tehát B_{k}(H, r) = B_{k}(H). ■

4.24 LEMMA. Legyen B_{k+1} ≤ H ≤ G és tegyük fel, hogy minden h ∈ H \ B_{k+1}-ra B_{k}(H) = B_{k}(h) vagy h + B_{k} ⊆ \overline{S(B_{k}(H))} Ekkor minden x ∈ G-re

π′_{k}|_{x+H} ∈ C_{AutΓ_{x}}(((B_{k})_{R})|_{x+H}) és υ_{k}^{π′_{k}} = τ′_{k},

ahol τ′_{k}|_{x+H} := τ_{k}|_{x+H}x_{R}^{∗}, υ′_{k}|_{x+H} := ((x^{∗})_{R})^{−1}υ_{k}|_{x+H}, V (Γ_{x}) := x+H és Γ_{x} ≅ Cay(H, S ∩ H)

Bizonyítás.Legyen y − x = h ∈ S ∩ H és válasszuk υ_{k} helyett υ′_{k} := (x_{R}^{∗})^{−1}υ-t. Erre ι_{k}(υ′_{k}) = ι_{k}(υ_{k}), (x + b)υ′_{k} − (x + b)τ = (x + b − x^{∗})υ_{k} − (x + b)τ = 0, tehát a^{∗} ∈ B_{k}(H) minden a ∈ x + H-ra és a 4.18 lemma (3) pontja szerint (y)π′_{k} − (x)π′_{k} ∈ y − x + B_{k}(H). B_{k}(h) = B_{k}(H) esetén a 4.16, h ∈ B_{k+1} esetén a 4.23 lemmából, egyébként pedig a feltételekből következik, hogy y−x ∈ \overline{S(B(H))}. Ezért y−x+0 ∈ S miatt y−x+B(H) ⊆ S és π′_{k} ∈ C_{AutΓ_{x}}(((B_{k})_{R})|_{x+H}). Végül a ∈ x + H-ra

(a)π′_{k}υ_{k}(π′_{k})^{−1} = (a)(x_{R}^{∗})^{−(a,g_{k})}π_{k}υ_{k}π_{k}^{−1}(x_{R}^{∗})^{(a,g_{k})+1} = (a)τ_{k}x_{R}^{∗}.
■

4.25 KÖVETKEZMÉNY. Z_{p}^{3} DCI-csoport

Bizonyítás. Legyen G = Z_{p}^{3}, Γ = Cay(G, S) és G_{R}^{δ} ≤ AutΓ. A 4.1 és 4.3 lemmák szerint υ_{1} = τ_{1} ∈ G_{R}. Ha B_{2}(g) = {0} minden g ∈ G-re akkor minden x ∈ G-re x^{∗} =: b ∈ B_{2}, (x)υ_{2}τ_{2}^{−1} = (x)b_{R}, és υ_{2} = τ_{2}b_{R} ∈ G_{R}. Ha valamilyen g ∈ G-re B_{2}(g) ≠ {0}, akkor B_{2}(g) = B_{2}, a 4.23 lemmából rg_{2} + B_{2} ⊆ \overline{S_{2}} (r = 1, …, p − 1) Ebből ⟨S_{2}⟩ ≠ G esetén g_{2} ∉ ⟨S_{2}⟩, a 4.18 és 4.19 lemmákból π_{2} ∈ C_{Aut(Γ)}(τ_{1}), υ_{2}^{π_{2}} = τ_{2}. Ha B_{2}(g) = B_{2}, akkor a 4.16 lemmából g + B_{2} ⊆ \overline{S_{2}}, azaz g ∉ S_{2}. Tehát g ∈ S_{2} esetén B_{2}(g) = 0, a 4.15 lemma szerint B(rg + tg′) ≤ B(g) + B(g′), amiből ⟨S_{2}⟩ = G mellett B_{2}(g) = {0} minden g ∈ G-re. Ha B_{3}(g_{3}) = {0}, akkor B_{3}(g) = {0} minden g ∈ G_{R} és mint előbb υ_{3} ∈ G_{R}. Ha B_{3}(g_{3}) ≠ {0}, akkor a 4.24 lemma szerint π′_{k} ∈ C_{Aut(Γ)}(⟨τ_{1}, τ_{2}⟩), (υ′)_{3}^{π′_{k}} = τ′_{3}. Végül a Babai lemmából Γ CI-gráf. ■

Foglajuk össze, hogy mit bizonyítottunk az imént.

4.26 LEMMA. Legyenek G = Z_{p}^{3}, Γ = Cay(G, S), ⟨G_{R}, G_{R}^{δ}⟩ ≤ P ∈ Syl_{p}(AutΓ). Ekkor

(1) π_{2} ∈ C_{Aut(Γ)}(τ_{1}) és ⟨S_{2}⟩ = G esetén υ_{2} ∈ G_{R}

(2) τ_{i} = υ_{i} (i = 1, 2) esetén π′_{3} ∈ C_{Aut(Γ)}(⟨τ_{2}, τ_{3}⟩)

Bizonyítás. Az elöbbi bizonyításból nyilvánvaló. ■

4.27 DEFINÍCIÓ. Legyen B_{k+1} ≤ H ≤ G . Ekkor h renitens H-ban, ha h ∈ H és B_{k}(h) ≠ B_{k}(H) vagy h + B_{k} ⊈ \overline{S(B_{k}(H))}, valamint az R_{k}(H) := ⟨h ∈ H|h renitens⟩ jelöléssel H renitens részcsoport, ha g_{k} ∈ R_{k}(H)

4.28 Megjegyzés. A 4.23 lemma szerint g_{k} nem renitens elem és B_{k}(B_{k}) = 0 figyelembevételével, ha van renitens elem, akkor minden b ∈ B_{k} is az.

4.29 LEMMA. Legyen B_{k+1} ≤ H ≤ G és tegyük fel, hogy H nem renitens. Ekkor alkalmas (·, ·)-el minden x ∈ G-re

π′_{k}|_{x+H} ∈ C_{AutΓ_{x}}(((B_{k})_{R})|_{x+H}) és υ_{k}^{π′_{k}} = τ′_{k},

τ′_{k}|_{x+H} := τ_{k}|_{x+H}x_{R}^{∗}, υ′_{k}|_{x+H} := ((x^{∗})_{R})^{−1}υ_{k}|_{x+H}, V (Γ_{x}) := x + H, Γ_{x} ≅ Cay(H, S ∩ H)

Bizonyítás. Legyenek y − x = h ∈ H ∩ S és válasszuk υ_{k} helyett υ′_{k} := (x_{R}^{∗})^{−1}υ-t. Erre ugyan úgy, mint a 4.24 bizonyításában ι_{k}(υ′_{k}) = ι_{k}(υ_{k}) és a^{∗} ∈ B_{k}(H) minden a ∈ x + Hra. Mivel g_{k} ∉ R_{k}(H) < G, ezért (·, ·) választható úgy, hogy g_{k} ∈ R_{k}(H)^{⊥}. Ekkor a 4.18 lemma (2) pontjából ha y − x ∈ R_{k}(H), akkor (y)π′_{k} − (x)π′_{k} ∈ S, a (3) pontjából pedig (y)π′_{k} − (x)π′_{k} ∈ y − x + B_{k}(H). Mivel y − x ∉ R_{k}(H) esetén y − x ∈ \overline{S(B_{k}(H))}, ezért y − x + 0 ∈ S miatt y − x + B_{k}(H) ⊆ S és π′_{k} ∈ C_{AutΓ_{x}}(((B_{k})_{R})|_{x+H}). A többi ugyan úgy adódik, mint a 4.24 bizonyításánál. ■

4.30 DEFINÍCIÓ. Legyenek H ≤ K ≤ G és T : P(G) × P(G) ⟶ P(G):

T (H, K) := (g ∈ G|g + K ⊆ \overline{S(H)}).

Minden g ∈ G-re definiáljuk a következő Cayley gráfokat

Γ(g, l) := Cay(B_{k}, T (B(g), B_{k}) ∩ B_{l} + B_{k}), Γ(g) := Γ(g, n + 1) (k ≤ l ≤ n + 1)

4.31 LEMMA. ι_{k}(G_{R}^{δ}) ∈ AutΓ(g)

Bizonyítás. Tegyük fel, hogy y − x + B_{k} ⊆ \overline{S(B(g))} és legyen (y)υ − (x)υ + b + b′ ∈ S, ahol υ ∈ G_{R}^{δ}, b ∈ B_{k}, b′ ∈ B(g)). Mivel G_{R}^{δ} centralizálja (B_{k})_{R}-t és része AutΓ-nak, ezért (y)υ+b+b′ = (y+b+b′)υ és y−x+b+b′ ∈ S, majd minden b′′ ∈ B(g)-re y−x+b+b′′ ∈ S és (y+b+b′′)υ−(x)υ = (y)υ−(x)υ+b+b′′ ∈ S. Másképp mondva Ξ_{B(g)}((y)υ−(x)υ+b) = 1 és ugyan így Ξ_{B(g)}(−((y)υ−(x)υ+b)) = 1. Tehát minden b ∈ B_{k}-ra (y)υ−(x)υ+b ∈ \overline{S(B(g))}. ■

4.32 LEMMA. Tegyük fel, hogy h_{i} ∉ ⟨h_{j}⟩ ∪ ⟨g_{k}⟩ (i, j ∈ {k, k + 1}) és ⟨g_{k}, g_{k+1}⟩ = ⟨h_{k}, h_{k+1}⟩. Ekkor

ι_{k}((B_{k+2})_{R}) ≠ ι_{k}(⟨υ_{k+1}, υ_{k}, (B_{k})_{R})⟩ ⇒ rh_{j} + B_{k} ⊆ \overline{S(B(h_{i}))} (i ≠ j)

Bizonyítás. Tekintsük a Γ(h_{i}, k + 2) gráfnak mondjuk azt a Γ′_{i} = Cay(H, T_{i}) részgráfját, ahol H := B_{k+2}/B_{k} és T_{i} = T (B(h_{i}), B_{k})∩B_{l} +B_{k}. Erre nyilván H_{R} = ι_{k}((B_{k+2})_{R})|\overline{B_{k+2}} és a 4.6 állításból a δ′ := ι_{k}(δ)|\overline{B_{k+2}} jelöléssel H_{R}^{δ′} = ι_{k}(⟨υ_{k+1}, υ_{k}, (B_{k})_{R})⟩|\overline{B_{k+2}}. A 4.31 lemmát felhasználva H_{R}^{δ′} ∈ AutΓ′, tehát

⟨H_{R}, H_{R}^{δ′}⟩ ≤ ι_{k}(P^{∗} ∩ kerι_{k+2})|\overline{B_{k+2}} ∩ AutΓ′ ≤ R ∈ Syl_{p}(AutΓ′)

majd a 4.21 lemmából r\overline{g_{k+1}} ∈ \overline{T_{i}(\overline{B_{k+1}})} (r = 1, …, p − 1). Eszerint, ha \overline{r_{1}g_{k+1} + t_{1}g_{k}} ∈ T_{i}, akkor \overline{r_{1}g_{k+1} + tg_{k}} ∈ T_{i} minden t ∈ F_{p}-re. Legyenek h_{i} = r_{i}g_{k+1} + t_{i}g_{k}, rh_{j} = r_{j}g_{k+1} + t_{j}g_{k} (r ≠ 0). A feltételek miatt r_{i} ≠ 0 ≠ r_{j}, tehát létezik r′ ∈ F_{p} \ {0}, hogy r′r_{i} = r_{j}. A 4.16 lemmából r′h_{i} + B_{k} ⊆ \overline{S(B(h_{i}))}, azaz \overline{r_{j}g_{k+1} + r′t_{i}g_{k}} ∈ T_{i}, és \overline{rh_{j}} = \overline{r_{j}g_{k+1} + t_{j}g_{k}} ∈ T_{i}. Másszóval rh_{j} + B_{k} ⊆ \overline{S(B(h_{i}))}. ■

4.33 TÉTEL. Z_{p}^{4} DCI-csoport

Bizonyítás. Legyen G = Z_{p}^{4}, Γ = Cay(G, S) és G_{R}^{δ} ≤ AutΓ. A 4.1 és 4.3 lemmák szerint υ_{1} = τ_{1} ∈ G_{R}. Mivel B_{2}(g) ≤ B_{2}(G) ≤ B_{2} és igy \overline{S_{2}} ⊆ \overline{S(B_{2}(G))} ezért itt g ∈ G csak úgy lehet renitens, ha g ∈ S_{2}, és a 4.16 lemmát alkalmazva g ∈ S_{2} mellett B_{2}(g) = 0. A 4.15 lemma szerint B(rg + th) ≤ B(g) + B(h), ezért az ⟨S_{2}⟩ = G esetben B_{2}(G) = {0}, az az nincs is renitens elem. Ha S_{2} ∩ B_{2}(G) ≠ {0}, akkor B_{2}(G) = B_{2} és a 4.23 lemmából g_{2} ∈ \overline{S_{2}}, tehát g_{2} ∉ S_{2} + B_{2}. Ebből az |⟨S_{2}⟩| ≤ p^{2} esetben g_{2} ∉ ⟨S_{2}⟩, az az G nem renitens. Kaptuk, hogy csak az |⟨S_{2}⟩| = p^{3} esetben lehet G renitens. Most az összes nem renitens esetben alkalmazva a 4.29 lemmát π_{2} ∈ C_{Aut(Γ)}(τ_{1}), υ_{2}^{π_{2}} = τ_{2}. Nézzük tovább ezeket az eseteket. Legyenek h_{i} := ig_{3} + g_{4} (i ∈ F_{p}). Ha {0} ≤ B_{3}(G) < B_{3}, akkor legfeljebb egy i-re lehet B_{3}(h_{i}) < B_{3}(G), mert különben a 4.15 lemmát használva minden g ∈ G-re B_{3}(g) ≤ B_{3}(h_{i}) + B_{3}(h_{j}) = {0}, amiből B_{3}(G) = {0} következne. Ekkor viszont g_{3} ∉ R_{3}(G), azaz G nem renitens. Ha B_{3}(G) = B_{3} és G renitens, akkor valamilyen j-re és r′ ∈ F \ \{0\}-re r′h_{j} + B_{3} ⊈ \overline{S(B_{3}(G))} = \overline{S_{3}}, tehát r′h_{j} ∉ \overline{S_{3}} és valamilyen i ≠ j-re r′h_{j} + B_{3} ⊈ \overline{S(B_{3}(h_{i}))}. Most a 4.32 lemmát alkalmazva azt kapjuk, hogy ι_{3}(G_{R}) = ι_{3}(G_{R}^{δ}). Tehát léteznek υ′_{t} ∈ G_{R}^{δ} (t ∈ {3, 4}), hogy a g′_{3} := r′h_{j} jelöléssel ι_{3}(υ′_{3}) = ι_{3}((g′_{3})_{R}) és ι_{4}(υ′_{4}) = ι_{4}((g′_{4})_{R}) valamilyen g′_{4} ∉ ⟨g_{1}, g_{2}, g′_{3}⟩-vel. Erre elmondva az előbbieket, B_{3}(G) = B_{3} nem fordulhat elő, mert különben a 4.23 lemmából g′_{3} = r′h_{j} ∈ \overline{S_{3}}-t kapnánk ellentmondásban az előbbiekkel. Tehát G itt már nem renitens és alkalmas υ′_{3}-vel mindig alkalmazhatjuk a 4.29 lemmát. Kaptuk, hogy τ_{i} = υ_{i} (i = 1, 2, 3) és ι_{4}(τ_{4}) = υ_{4}(τ_{4}). Ekkor további renitens elem csak B_{3}-ban lehet, G itt sem renitens és újra alkalmazva a 4.29 lemmát, G_{R} = G_{R}^{πδ}, π ∈ Aut(Γ). Maradt a renitens |⟨S_{2}⟩| = p^{3} eset. Legyen a H := ⟨S_{2}⟩ szerinti mellékosztályok egy reprezentáns rendszere X := {x_{1}, …, x_{p}} és tekintsük azokat a Γ_{x_{i}} részgráfokat, ahol V (Γ_{x_{i}}) := x_{i} + H és Γ_{x_{i}} ≅ Cay(H, S ∩ H). Ugyanúgy mint a bizonyítás elején R_{2}(H) = H esetén itt sincs renitens elem, az az H nem renitens, ahogy az |R_{2}(H)| ≤ p^{2} esetben sem az. Megint a 4.29 lemmát alkalmazva minden i ∈ F_{p}-re π′_{2}|_{x_{i}+H} ∈ C_{AutΓ_{x_{i}}}(((B_{2})_{R})|_{x_{i}+H}) és υ_{2}^{π′_{2}}|_{x_{i}+H} = τ_{k}|_{x_{i}+H}(x_{i}^{∗})_{R}. Tekintsünk egy Γ_{x_{i}}-t és legyen g_{3} ∈ H. Erre H ≅ Z_{p}^{3} és υ′_{i}|_{x_{i}+H} ∈ H_{R}|_{x_{i}+H} (i = 1, 2) miatt a 4.26 lemma (2) pontjából π′_{3}|_{x_{i}+H} ∈ C_{Aut(Γ_{x_{i}})}((B_{3})_{R}|_{x_{i}}). Ez azt jelenti, hogy y − x ∈ H ∩ S-ből (y)π′_{3} − (x)π′_{3} ∈ H ∩ S következik. Majd nézzük a Γ⃗_{2} = Cay(G/B_{2}, S⃗_{2}) segédgráfot, ahol (G/B_{2})_{R} = ι_{2}(G_{R}) és S⃗_{2} := \{\overline{g} ∈ G/B_{2}|g + B_{2} ⊆ S\}. Itt \overline{y} − \overline{x} ∈ S⃗_{2} \ \overline{H} pontosan azt jelenti, hogy y − x ∈ S \ H. Mivel ι_{2}(G_{R}^{δ}) ≤ ι_{2}(P) ≤ R ∈ Syl_{p}(AutΓ⃗), ezért a 4.26 lemma (1) pontjából ι_{2}(π′_{3}) ∈ C_{AutΓ⃗}(ι_{2}((B_{3})_{R})). Ez pedig azt jelenti, hogy \overline{y}−\overline{x} ∈ S⃗_{2}\\overline{H}-ból (\overline{y})ι_{2}(π′_{3})−(\overline{x})ι_{2}(π′_{3}) ∈ S⃗_{2}\\overline{H} következik. Ez utóbbi esetén viszont minden x′ ∈ x+B_{2}, y′ ∈ y+B_{2} párra (y′)(π′_{3})−(x′)(π′_{3}) ∈ S. Ebből (y)(π′_{3})−(x)(π′_{3}) ∈ S minden y−x ∈ S \H-ra és π′_{3} ∈ AutΓ. Tehát ott tartunk, hogy τ_{1} = υ_{1}, ι_{2}(τ_{j}) = ι_{2}(υ_{j}) (j = 2, 3) és υ_{j}|_{x_{i}+h} = τ_{j}|_{x_{i}+h}. Mivel g_{4} ∉ H < G, ezért a (·, ·)-t választhatjuk úgy, hogy g_{4} ∈ H^{⊥} is teljesüljön. Ha y − x ∈ S ∩ H, akkor a 4.18 lemma (2) pontjából, ha pedig y − x ∈ S \ H akkor a Γ⃗_{2} gráfot nézve a 4.26 lemma (2) pontjából következik, hogy (y)π′_{4} − (x)π′_{4} ∈ S, vagyis π′_{4} ∈ AutΓ. Erre viszont már υ_{4}^{π′_{4}} = τ_{4} és τ_{4}υ_{j}^{π′_{4}} = υ_{j}^{π′_{4}}τ_{4} figyelembevételével υ_{j} ∈ G_{R} (j = 1, 2, 3, 4). Ha g_{3} ∉ H, akkor (·, ·)-t rögtön választhatjuk úgy, hogy g_{3} ∈ H^{⊥} is teljesüljön, és itt elöbb a Γ⃗_{2} gráfot nézve jutunk el oda, hogy τ_{1} = υ_{1}, ι_{2}(τ_{j}) = ι_{2}(υ_{j}) (j = 2, 3). De itt már most τ_{3}υ_{2} = υ_{2}τ_{3}, tehát υ_{2}|_{ig_{4}+B_{3}} ∈ G_{R}|_{ig_{4}+B_{3}} és g_{4} ∈ H miatt υ_{j} ∈ G_{R} (j = 1, 2, 3). Korábban már láttuk, hogy itt is alkalmazható a 4.29 lemma, és így már minden esetben G_{R} = G_{R}^{πδ} valamilyen π ∈ Aut(Γ)-ra. Végül a Babai lemmát alkalmazva kapjuk,hogy Γ CI-gráf. ■

Irodalomjegyzék

[1] A.Ádám, Research problem 2-10, J. Combin. Theory 2 (1967), 393.

[2] N. Alon, Tools from higher algebra,Handbook of Combinatorics (in: R. L. Graham et al. Eds.), Elsevier Science, Amsterdam, 1995, pp. 1751–1783.

[3] B. Alspach and T. D. Parsonc, Isomorphisms of circulant graphs and digraphs, Discrete Math. 25 (1979), 97–108.

[4] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977), 329–336.

[5] L. Babai and P. Frankl, Isomorphism of Cayley graphs, I, Colloq. Math. Soc. J. Bolyai 18 (1978), 35–52.

[6] L. Babai and P. Frankl, Isomorphism of Cayley graphs, II, Acta Math. Acad. Sci. Hungar. 34 (1979), 177–183.

[7] L. Babai, Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics (in: R. L. Graham et al. Eds.), Elsevier Science, Amsterdam, 1995, pp. 1449–1540.

[8] N. Biggs, Algebraic Graph Theory, Cambridge University Press, New York, 1992.

[9] M. Conder and C. H. Li, On isomorphisms of finite Cayley graphs, European J. Combin. 19 (1998), 911-919.

[10] H.S.M. Coxeter, W.O.J. Moser, Generators and Relations for Discrete Groups, Springer, Berlin-Göttingen, 1957.

[11] B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Combin. Theory 9 (1970), 297–307.

[12] M. Hirasaka and M. Muzychuk, The elementary abelian group of rank 4 is a CI-group, J. Combin. Theory Ser. A 94 (2001), 339–362.

[13] C.H. Li, On isomorphisms of finite Cayley graphs — a survey, Discrete Math. 256 (2002), 301–334.

[14] C.H. Li, C.E. Praeger, M.Y. Xu, Isomorphism of finite Cayley digraphs of bounded valency, J. Combin. Theory Ser. B 73 (1998), 164–183.

[15] A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.

[16] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Progress in Mathematics, Vol. 125, Birkhäuser - Basel - Boston, Berlin, 1994.

[17] G. A. Margulis, Explicit constructions of graphs without short cycles and low density codes, Combinatorica 2 (1982), 71–78.

[18] Morris,Joy, Result towards showing Z_{p}^{n} is a CI-group, Congr. Numer. 156 (2002), 143–153.

[19] M. Muzychuk, Ádám’s conjecture is true in the square-free case, J. Combin. Theory Ser. A 72 (1995), 118–134.

[20] M. Muzychuk, On Ádám’s conjecture for circulant graphs, Discrete Math. 167/168 (1997), 497–510; corrigendum 176 (1997), 285–298.

[21] Muzychuk, M. An elementary abelian group of large rank is not a CI-group, Discrete Math. 264 (2003), 167–185.

[22] L. A. Nowitz, A non-Cayley-invariant Cayley graph of the elementary Abelian group of order 64, Discrete Math. 110 (1992), 223–228.

[23] P. P. Pálfy, Isomorphism problem for relational structures with a cyclic automorphism, European J. Combin. 8 (1987), 35–43.

[24] C.E. Praeger, Finite transitive permutation groups and finite vertex-transitive graphs, in: Graph Symmetry: Algebraic Methods and Applications, NATO ASI Series C, Vol. 97, 1997, pp. 277–318.

[25] G.O. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426–438.