- 1. feladat F Ö
A 84. ábra a 11.2
megoldásában mutatja, hogyan rendelhetjük hozzá a
K
5
éleit a
P
Petersen gráf pontjaihoz úgy, hogy
összekötött pontokhoz közös pont nélküli éleket
rendeljünk. Így
P
≅
L
K
5
¯
és a
P
automorfizmus csoportja ugyanaz, mint
az
L
K
5
-é. Az
L
K
5
izomorf a
K
5
automorfizmuscsoportjával. Ugyanis a
K
5
minden automorfizmusa indukálja az
élgráfjának egy automorfizmusát. Megfordítva, legyen
α
egy automorfizmusa az
L
K
5
-nek. Vegyük észre, hogy tetszőleges
L
K
5
4-elemű teljes részgráfja megfelel egy
csillagnak
K
5
-ben, és megfordítva, így
L
K
5
-nek pontosan öt 4-elemű teljes
részgráfja van, és
L
K
5
tetszőleges pontja egyértelműen meg
van határozva, mint valamely kettőnek a metszete. Így,
α
egy permutációját indukálja az
L
K
5
öt 4-elemű teljes részgráfjának és ez
a
K
5
egy automorfizmusát indukálja.
Így a
P
automorfizmuscsoportja izomorf a
K
5
automorfizmuscsoportjával, ami
S
5
. [R. Frucht, Comment. Math. Helv.
9
(1936–37) 217–223.]
- 2. feladat F Ö
(a) Ezen gráf minden automorfizmusa a dodekaéder
egy egybevágósága. Ez következik abból az
észrevételből, hogy egy pont csillagának tetszőleges,
másik pont csillagára történő leképezéséhez létezik egy
egyértelmű automorfizmus, mely ezt kiterjeszti; létezik
egy egyértelmű egybevágósága a dodekaédernek is, így az
automorfizmus ugyanaz kell, hogy legyen, mint amit az
egybevágóság indukál.
Ez az észrevétel azt is mutatja, hogy a
dodekaédernek 120 egybevágósága van.
Tekintsük az ötlettárbeli 16. ábrán mutatott
kockákat. Vegyük észre, mindegyik lapátló pontosan egy
kockának az éle, és minden kocka pontosan egy átlóját
tartalmazza mindegyik lapnak. Így, az ilyen kockák
száma pontosan 5. Legyenek
Q
1
,
…
,
Q
5
ezek a kockák. A dodekaéder minden
α
egybevágósága a
Q
1
,
…
,
Q
5
kockák egy
α
¯
permutációját indukálja. Tegyük fel,
hogy
α
¯
=
1
teljesül valamely
α
-ra. Tekintsük a dodekaédernek egy
tetszőleges
x
pontját. Ezt pontosan két kocka,
Q
i
és
Q
j
, tartalmazza. Ennek a két kockának
egyetlen további közös pontja van, nevezetesen az
x
′
, az
x
átlós ellenpárja. Így
α
x
=
x
vagy
x
′
. Továbbá, ha
α
x
=
x
valamely
x
-re, akkor az
x
minden
y
szomszédjára
α
y
-nak az
x
egy szomszédjának kell lennie, így
α
y
=
y
. Ebből következik, hogy
α
vagy az identitás, vagy a dodekaéder
ϱ
tükrözése a középpontra
vonatkozólag.
A dodekaéder egybevágóságainak a száma 120. A
fentiek miatt,
α
→
α
¯
a
Γ
egybevágósági csoport egy
homomorfizmusa az
S
5
-be, és a képnek 60 eleme van. Az
S
5
egyetlen 60-elemű részcsoportja az
A
5
alternáló csoport, így ez a
Γ
képe. A fenti meggondolások mutatják,
hogy a leképezés monomorf (injektív) az irányítást
megőrző egybevágóságok
Γ
0
részcsoportján, így ez a részcsoport
(melynek világos, hogy az indexe 2), izomorf
A
5
-tel. Az is következik, hogy
{
1
,
ϱ
}
egy normálosztó, és így ezért
ϱ
a
Γ
minden elemével kommutál. Így
(b) Ugyanígy, mint a dodekaéder esetén
következik, hogy a kocka minden automorfizmusát egy
egybevágóság indukálja, és maga az egész csoport a
Z
2
és a kocka irányítástartó
egybevágóságai csoportjának a direktszorzata. A kocka
minden irányítástartó egybevágósága a 4 főátló egy
permutációját indukálja. Azt is könnyű látni, hogy ha
egy irányítástartó egybevágóság minden főátlót önmagára
képez, akkor ez identitás. Ezért, a kocka
irányítástartó egybevágóságainak a csoportja az
S
4
-nek részcsoportja. Egyszerű számolás
mutatja, hogy a kockának 24 irányítástartó
egybevágósága van (minden élt pontosan két ilyen
egybevágóság visz tetszőleges másik élbe), és így az
irányítástartó egybevágóságok csoportja
S
4
.
Világos, hogy a tetraéder automorfizmuscsoportja
az
S
4
. Az oktaéder a kocka duálisa; mivel
az automorfizmusait ugyanúgy az egybevágóságok
indukálják, mint az előző esetben, az
automorfizmuscsoportja ugyanaz, mint a kockáé, azaz, a
Z
2
×
S
4
csoport. Hasonlóan, az ikozaéder
automorfizmus csoportja izomorf
Z
2
×
A
5
-tel.
- 3. feladat F Ö
Egy olyan gráfnak, mint ami a 86. ábrán
láthatóhoz hasonló, csak a forgatások az
automorfizmusai. [R. Frucht, Compositio Math.
6 (1938)
239–250.]
- 4. feladat F Ö
Tetszőleges, rögzített
g
csoportelemmel való szorzás jobbról,
azaz a
g
i
↦
g
i
g
leképezés automorfizmus: ha
g
i
össze van kötve
g
j
-vel egy
k
színű éllel (azaz
g
i
g
j
−
1
=
g
k
), akkor
g
i
g
g
j
g
−
1
=
g
k
és így,
g
i
g
össze van kötve
g
j
g
-vel egy
k
színű éllel.
Megfordítva, a
G
egy automorfizmusa ezen a módon
keletkezik. Mert legyen
α
a
G
tetszőleges automorfizmusa, és legyen
g
=
α
1
. Azt állítjuk, hogy
g
i
g
=
α
g
i
. Mivel
g
i
g
g
−
1
=
g
i
,
g
i
g
a
g
-vel egy
i
színű éllel van összekötve, és
g
i
az egyetlen ilyen tulajdonságú pont.
Másrészt,
g
i
az 1-gyel, definíció szerint egy
i
színű éllel van összekötve, és mivel
α
egy automorfizmus, ebből következik,
hogy
α
g
i
az
α
1
=
g
-vel egy
i
színű éllel van összekötve. Így,
α
g
i
=
g
i
g
.
Mivel könnyű látni, hogy a
Γ
elemeinek a szorzata ugyanaz, mint a
szorzás a
G
megfelelő automorfizmusai között,
ahhoz az eredményhez jutunk, hogy a
G
automorfizmuscsoportja izomorf
Γ
-val. [R. Frucht, ibid.].
- 5. feladat F Ö
Feltehetjük, hogy
Γ
≥
2
. Az előző probléma egy színezett,
irányított
G
→
0
gráfhoz vezet, melynek az
automorfizmuscsoportja izomorf
Γ
-val.
Ha
g
i
,
g
j
∈
V
G
→
0
=
Γ
egy
k
színű éllel vannak összekötve, akkor
kössük őket össze egy
k
+
2
hosszúságú úttal. Ezeknek az utaknak
minden belső pontjából egy 1 hosszúságú utat indítunk,
kivéve a
g
j
-vel szomszédos belső pontot, ahol egy
2 hosszúságú utat indítunk (87. ábra). Ezt minden
g
i
,
g
j
párra végrehajtjuk, és ezután
elhagyjuk az irányított éleket. Ezt a gráfot
G
-vel jelöljük.
Vegyük először is észre, hogy
G
→
0
minden automorfizmusa indukálja a
G
-nek egy egyértelműen meghatározott
automorfizmusát. Elegendő megmutatni, hogy megfordítva,
ha
α
egy automorfizmusa a
G
-nek, akkor
α
a
G
→
0
valamely automorfizmusából keletkezik.
V
G
→
0
pontjai éppen azok a pontjai
G
-nek, melyek se nem elvágó pontok, se
nem végpontok. Ebből következik, hogy
V
G
→
0
invariáns
A
G
-re vonatkozólag.
Az új utak, a hozzájuk ragasztott új utakkal, a
G
−
V
G
→
0
komponensei, így
α
egymásra képezi le őket. Egy
k
hosszúságú út egy
k
hosszúságú útra kell, hogy
leképződjön, és az út vége, melyhez a hosszabb út van
ragasztva, a megfelelő végre kell, hogy leképeződjön.
Így, ha
g
i
össze van kötve
g
j
-vel egy
k
színű éllel, akkor
α
g
i
is ugyanígy van összekötve
α
g
j
-vel. Így
α
a
G
→
0
egy automorfizmusát szolgáltatja,
ahogy állítottuk [R. Frucht, uo.].
- 6. feladat F Ö
Legyen
V
i
=
{
γ
,
i
:
γ
∈
Γ
}
i
=
1
,
2
. Tekintsük
Γ
-t, mely
V
1
∪
V
2
-n hat, az alábbiak szerint;
Legyen
h
1
,
…
,
h
m
a
Γ
egy minimális generáló halmaza. Tegyük
fel először, hogy
m
≥
2
. Kössük össze
1
,
1
-et
1
,
2
-vel,
h
1
,
2
-vel,
…
,
h
m
,
2
-vel,
h
1
,
1
-gyel. Kössük össze
h
1
,
2
-t
h
2
,
2
-vel …
h
m
,
2
-vel. Vegyük ezen élek összes képét,
mely a
Γ
által keletkezik, és jelöljük ezt
G
-vel.
Világos, hogy
Γ
minden eleme
G
-nek egy automorfizmusa lesz. Nézzük
meg, hogy van-e más is.
Legyen
α
a
G
-nek egy automorfizmusa, és tegyük fel
először, hogy
V
1
,
V
2
változatlan marad. A
Γ
egy megfelelő elemével szorozva,
elérhetjük, hogy
α
1
,
1
=
1
,
1
. Az
1
,
1
pont össze van kötve
1
,
2
-vel,
h
2
,
2
−
v
e
l
,
…
,
h
m
,
2
-vel a
V
2
-ben.
α
változatlanul kell, hogy hagyja ezt a
halmazt.
Azt állítjuk, hogy ezek a pontok az alábbi gráfot
feszítik ki:
1
,
2
izolált,
h
1
,
2
,
…
,
h
m
,
2
egy
P
utat alkotnak. Világos, hogy
P
élei
G
-ben vannak, de meg kell mutatnunk,
hogy nincs másik él ezek között a pontok között.
Pontosabban, megmutatjuk, hogy:
Γ
egyik
h
i
,
2
,
h
i
+
1
,
2
párt sem képezi le
h
r
,
2
,
h
s
,
2
-re, kivéve, ha
{
r
,
s
}
=
{
i
,
i
+
1
}
, és soha sem képezi
1
,
2
,
h
r
,
2
-re. Mert tegyük fel, hogy
Ekkor
γ
=
h
i
−
1
h
r
=
h
i
+
1
−
1
h
s
. Ha
r
,
s
egyike különbözik
h
i
és
h
i
+
1
-től is, akkor kifejezhető ebből a
relációból, ami ellentmond a
{
h
1
,
…
,
h
m
}
generáló halmaz minimalitásának. Így
{
r
,
s
}
=
{
i
,
i
+
1
}
. A másik állítás hasonlóan
következik.
Ebből következik, hogy
α
fixen kell, hogy hagyja
1
,
2
-et, és hogy két lehetősége van
α
-nak, ahova leképezi
h
1
,
2
,
…
,
h
m
,
2
-et: vagy
α
az identitás ezen a halmazon, vagy
α
h
i
,
2
=
h
m
−
i
+
1
,
2
. A második lehetőséget a
következőképpen zárhatjuk ki.
h
1
,
2
össze van kötve
h
1
,
1
-gyel, mely az
1
,
2
szomszédja. Megmutatjuk, hogy
h
m
,
2
nincs összekötve az
1
,
1
egyik szomszédjával sem
V
1
-ben. Valóban,
1
,
1
-nek van két (nem szükségképpen
különböző) szomszédja
V
1
-ben,
h
1
,
1
és
h
1
−
1
,
1
. Ha
h
1
±
1
,
1
össze lenne kötve
h
m
,
2
-vel, akkor
h
1
±
1
,
1
=
γ
1
,
1
, vagy
h
m
,
2
=
γ
h
r
,
2
, vagy
h
m
,
2
=
γ
1
,
2
teljesülne valamely
γ
∈
Γ
-ra, és
1
≤
r
≤
m
. De ebből következne, hogy
γ
=
h
1
±
1
, és vagy
γ
=
h
r
−
1
h
m
, vagy
γ
=
h
m
teljesülne, de ezek mindegyike
lehetetlen a
{
h
1
,
…
,
h
m
}
generáló halmaz minimalitása
miatt.
Ezzel beláttuk, hogy ha
α
fixen hagyja
1
,
1
-et, akkor fixen hagyja a
V
2
-beli szomszédait is. Most
megmutatjuk, hogy
α
a
V
1
-en és
V
2
-n ugyanúgy hat, azaz, ha
α
g
,
1
=
g
′
,
1
, akkor
α
g
,
2
=
g
′
,
2
. Valóban,
g
α
g
′
−
1
az
1
,
1
-et fixen tartja, és ebből, ugyanúgy,
mint fentebb, következik, hogy fixen hagyja
1
,
2
-t is. De ez azt jelenti, hogy
α
g
,
2
=
g
′
,
2
. Így
α
fixen hagyja
h
1
,
1
,
…
,
h
m
,
1
-et. Ekkor következik, hogy ha
α
fixen hagyja
g
,
1
-et, akkor fixen hagyja
g
h
i
,
1
-et is minden
i
=
1
,
…
,
m
-re. Mivel
{
h
1
,
…
,
h
m
}
generálja
Γ
-t, következik, hogy
α
fixen hagyja
V
1
minden elemét. Amint láttuk, ebből
következik, hogy fixen hagyja a
V
2
minden elemét is, azaz,
α
=
1
. Ez bizonyítja, hogy a
G
azon automorfizmusai, melyek a
V
1
és
V
2
-t invariánsan hagyják, csak a
Γ
elemei lehetnek.
Ahhoz, hogy kizárjuk a
G
azon automorfizmusait, melyek nem
hagynák
V
1
és
V
2
-t invariánsan, úgy akarjuk elrendezni
a fokokat ezekben a halmazokban, hogy különbözők
legyenek. Ha már ez teljesül magára
G
-re, akkor készen vagyunk. Különben,
komplementáljuk
V
1
-ben. Mivel
G
-ben a
V
1
által kifeszített részgráf fokai
legfeljebb 2 nagyságúak, a komplementerben legalább
n
−
1
−
2
>
2
nagyságúak lesznek. Így minden fokszám
növekszik, ezért a komplementálás után nem lesznek
egyenlőek a
V
2
-beli fokokkal. Mivel a komplementálás
a
V
1
-ben nem befolyásolja azon
automorfizmusokat, melyek a
V
1
-et invariánsan hagyják, a kívánt
tulajdonságú gráfot kapjuk.
Abban az esetben, amikor
m
=
1
, azaz
Γ
ciklikus, vegyük a 88. ábrán látható
gráfot. A külső körön lévő pontok foka 5, a belső
pontok foka 3, így minden automorfizmus a külső kört
önmagára képezi le. A belső pontok megakadályozzák a
tükrözéseket. [L. Babai, Can. Math. Bull.
17 (1974)
467–470.]
- 7. feladat F Ö
(a) Tegyük fel indirekt módon, hogy egy
T
turnamentnek páros sok automorfizmusa
van. A Cauchy tétel miatt ekkor
T
-nek van egy másodrendű
α
automorfizmusa. Legyen
x
y
egy 2 hosszúságú ciklusa
α
-nak. Mivel
γ
egy turnament, vagy
x
,
y
, vagy
y
,
x
éle
T
-nek, de nem mindkettő. Mondjuk
x
,
y
∈
E
T
, ekkor
α
az
x
,
y
élt
y
,
x
∉
E
T
-re képezi le, ami
ellentmondás.
(b) Vegyük észre először a következő tényt.
Legyen
V
egy olyan halmaz, hogy a
Γ
, páratlan rendű csoport regulárisan
hat
V
-n. Tekintsük a
Γ
pályáit a rendezett párok
x
,
y
,
x
≠
y
,
x
,
y
∈
V
,
E
halmazán. Nincs a
Γ
-nak olyan eleme, mely
x
,
y
-t az
y
,
x
-re képezné le; mert egy ilyen
permutáció tartalmazna egy páros ciklust, és így páros
rendű lenne.
Így a
Γ
pályái az
E
-n, beoszthatók
{
S
,
S
′
}
párokba, melyekre
S
′
=
{
x
,
y
:
y
,
x
∈
S
}
teljesül. Kiválasztva minden ilyen
{
S
,
S
′
}
párból egy pályát, ezen pályák uniója
egy
T
turnamentet fog alkotni, mely
Γ
minden elemét automorfizmusként fogja
tartalmazni. Vegyünk két
V
i
=
{
α
,
i
:
α
∈
Γ
}
i
=
1
,
2
halmazt, és definiáljuk az
α
∈
Γ
hatását a
V
1
∪
V
2
-n a következőképpen:
Legyen
h
1
,
…
,
h
m
a
Γ
egy minimális generáló halmaza.
Kössük össze
γ
,
1
-et
δ
,
2
-vel, ha
δ
=
γ
, vagy
δ
=
γ
⋅
h
i
1
≤
i
≤
m
, és
δ
,
2
-t
γ
,
1
-gyel különben. Vegyünk egy
tetszőleges turnamentet
V
1
-n, mely invariáns
Γ
-re . Ahhoz, hogy definiáljuk a
turnamentet
V
2
-n, vegyük észre, hogy nincs olyan
h
i
,
2
,
h
j
,
2
vagy
h
i
,
2
,
1
,
2
vagy
1
,
2
,
h
i
,
2
pár, mely egy ilyen párra lenne
leképezve, egy tetszőleges
γ
∈
Γ
,
γ
≠
1
elem által; mert például
azt eredményezné, hogy
amiből következik a
{
h
1
,
…
,
h
m
}
minimalitása miatt, hogy vagy
i
=
ν
,
j
=
μ
és így
h
i
h
j
2
=
1
(amit kizártunk, mert
Γ
páratlan rendű) vagy
i
=
μ
,
j
=
ν
és így
γ
=
1
. Így vehetjük az
1
,
2
,
h
i
,
2
i
=
1
,
…
,
m
és
h
i
,
2
,
h
j
,
2
éleket
1
≤
i
<
j
≤
m
, és az összes képüket
Γ
által, és ahogy megjegyeztük az
elején, a
Γ
E
-n levő pályáinak minden maradék
párjának egyikét is véve, olyan turnamentet kapunk
V
2
-n, mely invariáns
Γ
-ra. Így definiáltunk egy
T
turnamentet
V
1
∪
V
2
-n, mely invariáns
Γ
-ra.
Azt állítjuk, hogy
A
T
=
Γ
. Legyen
α
∈
A
T
, meg akarjuk mutatni, hogy
α
∈
Γ
. Először vegyük észre, hogy a
V
1
pontjainak a kifoka
míg a
V
2
pontjainak a kifoka
ami különböző, mert
n
páratlan. Ezért, az
α
automorfizmus
V
1
-et és
V
2
-t invariánsan kell, hogy
hagyja.
Feltehetjük, hogy
α
1
,
1
=
1
,
1
. Ekkor azon
V
2
-beli pontok halmaza, melyek
elérhetőek
1
,
1
-ből egy élen, szintén invariáns
α
-ra. Ez a halmaz
1
,
2
,
h
1
,
2
,
…
,
h
m
,
2
-ből áll, ami egy tranzitív turnament.
Ezért
α
-nak mindezeket a pontokat fixen kell
hagynia. Ezért, ugyanúgy, mint az előző megoldásban,
következik, hogy
α
minden pontot fixen hagy, azaz,
α
=
1
. [J. W. Moon, Canad. J. Math.
16
(1964) 485–489; ez a konstrukció Babai Lászlótól
származik.]
- 8. feladat F Ö
A 87. ábrán mutatott utak helyett használjuk a
89. ábrán látható utakat ahhoz, hogy a
g
i
-t
g
j
-vel összekössük, ha össze vannak
kötve egy irányított,
k
színű éllel; ahol a 6-pontú
konfigurációt megismételjük
k
-szor. Ily módon kapunk egy
G
1
gráfot, melynek automorfizmus
csoportja
Γ
(ez pontosan úgy következik, mint
előbb). Azonban,
G
1
nem 3-reguláris, mivel a
V
G
0
pontjainak a foka
2
Γ
.
Vegyünk egy tetszőleges
g
i
∈
V
G
0
-t. Jegyezzük meg, hogy pontosan
kettő, a 89. ábrabeli
k
hosszúságú füzért illesztünk hozzá,
egyet, mindegyik típusú végződéssel
k
=
1
,
…
,
Γ
. Vágjuk szét
g
i
-t
2
Γ
, 1-fokú pontra; jelölhetjük őket a
következőképpen:
a
1
,
6
,
…
,
a
Γ
,
6
,
a
1
,
8
,
…
,
a
Γ
,
s
, ahol
a
k
,
j
egy a 89. ábrabeli
k
hosszúságú füzér, egy
j
-pontú konfigurációval az
a
k
,
j
mellett. Kössük össze az
a
k
,
j
-ket egy
C
i
körrel a fenti sorrendben. Tegyük ezt
meg minden
i
=
1
,
…
,
Γ
értékre. Világos, hogy a
G
1
minden automorfizmusa indukál egy
automorfizmust az eredményül kapott
G
gráfban. Megfordítva, legyen
α
a
G
egy automorfizmusa.
G
-ben háromszögek csak a 89. ábrabeli
„füzérekben” szerepelhetnek, így
α
egymásra képezi le őket; továbbá
azoknak a háromszögeknek, melyek a 6 pontú
konfigurációkban szerepelnek, különbözik a
szomszédságuk a 8 pontú konfigurációkban szereplőkétől,
és így
α
a 6 pontú konfigurációkat 6 pontú
konfigurációkra kell, hogy leképezze, és a 8 pontú
konfigurációkat 8 pontú konfigurációkra. Így
α
a maradékot, azaz a
C
i
körökön lévő pontokat egymásra képezi
le. Mivel a
C
i
-k a
V
C
1
∪
…
∪
V
C
Γ
által kifeszített részgráf
komponensei,
α
mindegyik
C
i
-t valamely
C
j
-re képezi le. Így,
α
egy (egyértelmű) automorfizmusát
indukálja annak a gráfnak, melyet a mindegyik
C
i
kontrakciójával kapunk. De ez a gráf
éppen
G
1
.
Így a
G
és a
G
1
automorfizmusai kölcsönösen
egyértelműen vannak egymásnak megfeleltetve, ami
nyilvánvalóan egy izomorfizmus. Így a
G
automorfizmuscsoportja izomorf
Γ
-val. Mivel
G
3-reguláris, készen is vagyunk. [R.
Frucht, Canad. J. Math.
1 (1949) 365–378. Ez a
bizonyítás Babai Lászlótól származik. Reguláris
gráfokra, tetszőleges fok esetén, lásd
G. Sabidussi, Canad. J. Math.
9 (1957)
515–525.]
- 9. feladat F Ö
Legyen
x
1
,
…
,
x
n
olyan, mint az ötlettárban, és
jelöljük
Γ
i
-vel azon automorfizmusok csoportját,
melyek fixen hagyják
x
1
,
…
,
x
i
-t. Ekkor
Γ
1
=
A
G
, mert
x
1
az egyetlen másodfokú pont, és így
minden automorfizmusnak fixen kell hagynia;
Γ
n
=
{
1
}
. Megmutatjuk, hogy a
Γ
i
−
1
:
Γ
i
index vagy 1 vagy 2; ebből már
következik az állítás.
Nézzük az
x
i
képeit
Γ
i
−
1
i
≥
2
által. Legyen
j
<
i
olyan, hogy
x
j
össze van kötve
x
i
-vel. Ekkor
x
j
-nek legfeljebb egy másik szomszédja
van az
{
x
i
,
…
,
x
n
}
halmazban. Mivel minden
γ
∈
Γ
i
−
1
az
x
i
-t az
x
j
egy ilyen szomszédjára kell, hogy
leképezze, következik, hogy
x
i
vagy fixen marad mindegyik
Γ
i
−
1
-beli automorfizmus hatására, vagy van
egy másik képe. A
Γ
i
−
1
:
Γ
i
index, ennek megfelelően, vagy 1, vagy
2.
Megjegyzés: Minden
2
k
-adrendű csoport fellép, mint egy
ilyen gráf automorfizmus csoportja. [cf. L. Babai–L.
Lovász, Studia Sci. Math. Hung.
8 (1973)
141–150].
- 10. feladat F Ö
Válasszunk ki egy
e
∈
E
G
élt, és irányítsuk tetszőlegesen.
Legyen
f
tetszőleges másik eleme az
e
pályájának, és legyen
α
az az egyértelmű automorfizmus, mely
e
-t
f
-re képezi le. Irányítsuk
f
-et úgy, hogy
α
megőrizze
e
irányítását, ha
α
∈
Γ
és megfordítja különben. A
G
maradék éleit oly módon irányítjuk,
hogy minden
γ
∈
A
G
megőrizze az irányításukat (ez
megtehető, mert
A
G
félig regulárisan hat
E
G
-n).
Az eredményül kapott irányított
G
→
gráfon a
Γ
elemei automorfizmusként hatnak, a
konstrukció szerint. Másrészt, legyen
α
a
G
→
tetszőleges automorfizmusa. Világos,
hogy
α
egy automorfizmusa a
G
-nek, azaz
α
∈
A
G
. Mivel
α
e
ugyanúgy van irányítva, mint
e
, következik, hogy
α
∈
Γ
[cf. J. Nešetřil, Monatsh. f. Math.
76 (1972) 323–327].
- 11. feladat F Ö
Könnyű ellenőrizni 12.5-ben, hogy ha elhagyunk
egy
e
élt, mely egy elsőfokú pontot köt
össze egy másodfokú ponttal, egy olyan gráfot nyerünk,
melynek nincs automorfizmusa. Véve a komplementerét,
kapunk egy összefüggő
G
2
gráfot, és egy
e
=
u
,
v
∈
E
G
2
élt, melyre
A
G
2
=
{
1
}
,
A
G
2
−
e
≅
Γ
2
. A 12.5-beli konstrukciónak megvan az
a tulajdonsága, hogy az automorfizmuscsoportja félig
regulárisan hat a pontokon, azaz nincs olyan
α
≠
1
automorfizmus, mely fixen hagyna akár
csak egy pontot is. Így van egy olyan
G
1
gráfunk, melyre
A
G
1
≅
Γ
1
és csak az identitás hagy fixen egy
bizonyos
x
∈
V
G
1
-t.
Konstruáljuk meg
G
-t a következőképpen. Legyenek a
pontjai az
x
1
,
x
2
párok, ahol
x
i
∈
V
G
i
. Továbbá, kössük össze
x
1
,
x
2
-et
y
1
,
y
2
-gyel, ha vagy
x
1
,
y
1
∈
E
G
1
vagy
x
1
=
y
1
és
x
2
,
y
2
∈
E
G
2
. (
G
-t a
G
1
és
G
2
lexikografikus szorzatának nevezzük.)
Még színezzük is ki az olyan
x
1
,
x
2
,
y
1
,
y
2
éleket pirosra, melyekben
x
1
=
y
1
, és a maradékot feketére. Állítjuk,
hogy
A
G
≅
Γ
1
. Nyilvánvalóan a
G
1
minden automorfizmusa indukálja
G
-nek egy automorfizmusát. Másrészt,
legyen
α
∈
A
G
. Mivel
G
2
összefüggő, a piros színű élek
kikényszerítik, hogy
α
-nak minden
V
x
1
=
{
x
1
,
x
2
:
x
2
∈
V
G
2
}
osztályt egy ilyen
V
x
1
′
osztályra kell leképeznie. Abból a
tényből, hogy
G
2
-nek nincs más automorfizmusa, mint az
identitás, következik, hogy
α
x
1
,
x
2
=
x
1
′
,
x
2
, azaz, hogy
α
-t a
G
1
egy automorfizmusa indukálja.
Másrészt, hagyjuk el az
f
=
x
,
u
,
x
,
v
élt. Ekkor minden
γ
∈
A
G
2
−
e
-re az a
γ
leképezés, melyet a következőképpen
definiálunk
automorfizmusa a
G
−
f
-nek. Megfordítva, ha
α
egy tetszőleges automorfizmusa a
G
−
f
-nek, akkor következik úgy, mint
fentebb, hogy
α
a
V
x
1
-et a
V
x
1
′
-re képezi le. De ekkor
α
-nak a
V
x
-et önmagára kell leképeznie (hiszen
V
x
kevesebb élt feszít ki, mint
akármelyik másik
V
x
1
). Ezért,
α
egy
α
˜
automorfizmusát indukálja a
G
1
-nek, mely fixen hagyja
x
-et, amiből következik, hogy
α
˜
=
1
, azaz,
α
V
x
1
=
V
x
1
teljesül minden
x
1
∈
V
G
1
-re. Mivel
V
x
1
egy olyan gráfot feszít ki, melynek
nincs nemtriviális automorfizmusa
x
1
≠
x
esetén, ahhoz jutunk, hogy
α
=
γ
¯
valamely
γ
∈
A
G
2
−
e
-re. Így
A
G
−
f
≅
Γ
2
.
Még meg kell valahogy szabadulnunk az élek
színezésétől. Ez könnyen megtehető, ha minden fekete
élt egy
N
hosszúságú úttal helyettesítünk, ahol
N
nagy [L. Babai].
- 12. feladat F Ö
(a) Mutassuk meg először, hogy létezik egy olyan
T
fa, melyre teljesül, hogy a
Γ
minden pályája pontosan egy pontját
tartalmazza a
T
-nek. Válasszunk ugyanis egy olyan
maximális
T
0
fát, melyből minden pálya legfeljebb
egy pontot tartalmaz. Ha
V
0
=
⋃
γ
∈
Γ
γ
V
T
0
=
V
G
, akkor készen vagyunk. Tegyük fel,
hogy
V
0
≠
V
G
, ekkor, mivel
G
összefüggő, létezik egy
x
∉
V
0
pont, mely össze van kötve valamely
y
∈
V
0
ponttal. Legyen
y
∈
γ
T
0
, ekkor
γ
T
0
+
x
,
y
egy nagyobb fa, mely minden pályát
legfeljebb egy pontban metsz.
Így messe a
T
fa mindegyik pályát pontosan egy
pontban. Húzzuk össze mindegyik
γ
T
-t,
γ
∈
Γ
. Az eredményül kapott
G
′
gráf, nyilvánvalóan, összefüggő, és
Γ
regulárisan hat rajta. [L. Babai, Acta
Math. Acad. Sci. Hung. 24
(1973) 215–221; cf. G.
Sabidussi, Proc. AMS
9 (1958) 800–804.]
(b) Indukciót használunk
V
G
-re vonatkozóan. Feltehetjük, hogy
Γ
≠
{
1
}
. Legyen
e
∈
E
G
egy olyan él, melynek legalább az
egyik végpontja nem fixpontja
Γ
-nak.
Legyen
G
′
a
G
-nek azon részgráfja, melyet a
G
γ
e
alakú élei alkotnak,
γ
∈
Γ
. Ekkor
G
′
a
G
-nek egy olyan részgráfja, melyen a
Γ
él-tranzitívan hat. Továbbá, a a
Γ
különböző elemeinek különböző a
hatásuk
V
G
′
-n; mert azon
γ
∈
Γ
permutációk halmaza, melyekre
teljesül, hogy
γ
|
V
G
′
=
1
a
Γ
-nak egy normális részcsoportját
alkotják; mivel
Γ
egyszerű, ezért vagy
N
=
Γ
, vagy
N
=
{
1
}
. Azonban,
N
=
Γ
-ból az következne, hogy
V
G
′
minden pontja, így az
e
él két végpontja is, fixpontjai a
Γ
-nak, ami ellentmondás. Így, ha
G
′
összefüggő, akkor készen
vagyunk.
Tegyük fel, hogy
G
′
nem összefüggő; legyenek
G
1
,
…
,
G
k
a komponensei. Ekkor
egy olyan partíciója a
V
G
-nek, mely invariáns a
Γ
-ra. Húzzuk össze mindegyik
G
i
-t egyetlen pontra. Az eredményül
kapott
G
″
gráf nyilvánvalóan összefüggő. Minden
γ
∈
Γ
automorfizmus indukál egy
γ
˜
∈
A
G
″
automorfizmust. Mint fentebb, mivel
Γ
egyszerű, ebből következik, hogy vagy
γ
˜
=
1
teljesül minden
γ
∈
Γ
-ra, vagy
γ
↦
γ
˜
egy-egyértelmű. De az előző lehetőség
nem fordulhat elő, mivel valamelyik
γ
∈
Γ
a
G
1
-et
G
2
-re képezi le, és erre
γ
˜
≠
1
teljesül. Így
A
G
″
tartalmaz egy részcsoportot, mely
izomorf
Γ
-val . Innen az állítás az indukciós
feltevés miatt következik. [L. Babai,
Discrete Math. 8
(1974) 13–20.]
- 13. feladat F Ö
Ha egy permutációcsoport kommutatív és tranzitív,
akkor reguláris (lásd a 11.17 megoldásához tett
lábjegyzetet).
Ha rögzítünk egy tetszőleges
x
0
-t, akkor az
A
G
regularitása miatt, minden
x
∈
V
G
egyértelműen írható fel
α
x
0
alakban, ahol
α
∈
A
G
. Így az a
ϕ
leképezés, melyre
ϕ
α
x
0
=
α
−
1
x
0
teljesül, jól meg van határozva, és
permutációja a
V
G
-nek. Továbbá,
ϕ
automorfizmusa a
G
-nek, mivel ha
x
,
y
∈
E
G
,
x
=
α
x
0
,
y
=
β
x
0
,
α
,
β
∈
A
G
akkor, mivel
α
automorfizmus,
x
0
,
α
−
1
β
x
0
=
x
0
,
β
α
−
1
x
0
∈
E
G
, ebből
β
−
1
x
0
,
α
−
1
x
0
∈
E
G
. Mivel
ϕ
fixen tartja
x
0
-t, az
A
G
regularitása miatt kapjuk, hogy
ϕ
=
1
. Így
α
−
1
=
α
minden
α
∈
A
G
-re, azaz az
A
G
minden eleme másodrendű. A
csoportelméletből jól ismert, hogy ebből következik,
hogy
A
G
másodrendű ciklikus csoportoknak a
direkt szorzata. [C. Y. Chao, Proc. AMS
15 (1964)
291–292; G. Sabidussi, Monatsh. f. Math.
68 (1964)
426–438.]
(b) Legyen
Q
n
az
n
-dimenziós kocka. Feltehetjük, hogy
Q
n
csúcsai
n
hosszúságú 01-vektorok, és két ilyen
vektor akkor és csak akkor van összekötve, ha pontosan
egy helyen különböznek. Jelöljük
e
I
-vel az
I
⊆
{
1
,
…
,
n
}
karakterisztikus vektorát. Ha egy
I
⊆
{
1
,
…
,
n
}
részhalmazhoz tartozó koordinátákban
felcseréljük a 0-t és 1-et, a
Q
n
-nek egy
α
I
automorfizmusát kapjuk. Az összes
α
I
automorfizmus
Γ
0
csoportja izomorf a
Z
2
×
…
×
Z
2
︸
n
csoporttal. Azonban,
Q
n
-nek van más automorfizmusa is,
például a két első koordináta felcserélése. Hogy ezeket
kizárjuk, változtassuk meg
Q
n
-et a következőképpen; kössünk össze
két vektort
k
éllel, ha csak a
k
-ik helyen különböznek. Világos, hogy
a fentebb definiált
α
I
továbbra is egy automorfizmusa az
eredményül kapott
Q
n
′
gráfnak. Megmutatjuk, hogy
Q
n
′
-nek nincs más automorfizmusa. Ha
lenne, akkor feltehetnénk, hogy van egy olyan, amelyik
fixen tartja a
0
,
…
,
0
-át. Azonban, ha
α
egy automorfizmus, amely fixen tartja
0
,
…
,
0
-át, akkor fixen tartja az
1
,
0
,
…
,
0
-át is, mivel ez az egyetlen olyan
pont, mely össze van kötve a
0
,
…
,
0
-val pontosan egy éllel. Hasonlóan,
fixen tartja
0
,
…
,
0
,
1
,
0
,
…
,
0
-t, az 1 tetszőleges pozíciója esetén.
Így, ha
α
fixen hagy egy pontot, akkor fixen
hagyja ennek az összes szomszédját is. Mivel
Q
n
′
összefüggő, ezért
α
fixen kell tartson minden pontot,
azaz,
α
=
1
, ami ellentmondás.
(c) Hozzá akarunk venni új éleket a
Q
n
-hez úgy, hogy a keletkező egyszerű
G
gráfnak továbbra is minden
α
I
automorfizmusa, de más automorfizmusa
nincs. Legyen
H
egy gráf az
{
e
1
,
…
,
e
n
}
vektorok halmazán, ahol
e
i
=
0
,
…
,
0
,
1
,
0
,
…
,
0
.
Ha
e
i
,
e
j
∈
E
H
, akkor
α
I
e
i
=
e
I
△
{
i
}
,
α
I
e
j
=
e
i
△
{
j
}
. Így ha az összes olyan
e
I
,
e
J
élt hozzávesszük
Q
n
-hez, melyre
I
△
J
=
{
i
,
j
}
melyre
e
i
,
e
j
∈
E
H
, egy olyan
G
gráfot kapunk, mely invariáns
Γ
0
hatása alatt.
Nézzük meg, hogy
H
-nak milyen tulajdonságokkal kell
rendelkeznie, ahhoz, hogy
G
-nek ne legyen más
automorfizmusa.
Tegyük fel, hogy
A
G
≠
Γ
0
. Mivel
Γ
0
tranzitív, van egy
α
∈
A
G
,
α
≠
1
, melyre
α
0
,
…
,
0
=
0
,
…
,
0
teljesül. Legyen
H
1
a
0
,
…
,
0
szomszédai által kifeszített gráf
G
-ben. Ez, persze, nem a
H
, mivel a
0
,
…
,
0
-nak van más szomszédja is, mint az
e
i
csúcsok:
H
1
pontjai az
e
1
,
…
,
e
n
és minden
e
{
i
,
j
}
pont, ahol
e
i
,
e
j
∈
E
H
. Két
e
i
alakú pont akkor és csak akkor van
összekötve, ha össze vannak kötve
H
-ban, és
e
{
i
,
j
}
akkor és csak akkor van összekötve
e
{
μ
,
ν
}
-vel, ha
e
i
,
e
j
,
e
μ
,
e
ν
csatlakozó élek, például
j
=
ν
és
e
i
,
e
μ
∈
E
G
.
Így
H
1
a
H
-ból úgy keletkezik, hogy veszünk egy
új
p
e
pontot a
H
minden
e
élére, és összekötjük az
e
végpontjaival, és egy
p
e
-t egy
p
e
′
-vel akkor és csak akkor kötünk össze,
ha
e
, és
e
′
egy háromszög élei a
H
-ban.
Vegyük észre, hogy ha
H
nem tartalmaz háromszöget, akkor a
V
H
1
−
V
H
minden pontja másodfokú. Ha
H
-nak nincs elsőfokú pontja, akkor csak
ezek a pontok másodfokúak. Ha ehhez még
H
aszimmetrikus is, akkor
H
1
is az.
Ha ezt el tudjuk érni, akkor készen vagyunk,
mivel ez azt jelenti, hogy
α
fixen hagyja a
0
,
…
,
0
szomszédait
G
-ben, és mivel
G
összefüggő, ezért minden pont fixen
marad, ami ellentmondás. Így mindössze egy
háromszögmentes, aszimmetrikus gráfra van szükségünk,
melyben nincs elsőfokú pont.
A 90. ábra egy ilyen
H
gráfot mutat
n
≥
8
esetére. [W. Imrich, Monatsh. f. Math.
73
(1969) 341–347. Olyan gráfokra, melyeknek az
automorfizmuscsoportja reguláris, de nem kommutatív,
lásd L. A. Nowitz–M. E. Watkins,
Canad. J. Math. 24
(1972) 993–1018.]
- 14. feladat F Ö
Legyen
G
pontosan
k
-szorosan élösszefüggő, és
X
⊆
V
G
egy minimális halmaz, melyre
δ
G
X
=
k
.
Az
X
minimalitása miatt,
X
≤
V
G
∕
2
. Legyen
x
1
,
x
2
∈
X
és
α
∈
A
G
olyan, hogy
α
az
x
1
-et
x
2
-be viszi. Legyen
α
X
=
X
′
. Ekkor
δ
G
X
′
=
k
(mert
α
egy automorfizmus) és
X
∩
X
′
≠
∅
és
X
∪
X
′
≠
V
G
(mivel
X
=
X
′
≤
V
G
∕
2
). Így 6.48a miatt,
δ
G
X
∩
X
′
=
k
. Mivel
X
minimális, ez csak akkor lehetséges,
ha
X
∩
X
′
=
X
, i.e.
X
=
X
′
.
Így azok az automorfizmusok, melyek
X
-et invariánsan tartják, tranzitívan
hatnak
X
-en. Ebből az következik, hogy
X
minden pontjának ugyanannyi,
a
számú, szomszédja van
X
-ben. Nyilvánvalóan,
és mivel
X
minden pontja össze van kötve
r
−
a
ponttal az
X
-en kívül,
Így
Mivel nyilvánvaló, hogy
r
≥
k
, kapjuk, hogy
r
=
k
, mint állítottuk.
- 15. feladat F Ö
(a) Legyen
T
⊆
V
G
,
T
=
3
,
G
1
a
G
−
T
egy komponense,
X
=
V
G
1
és tegyük fel, hogy
T
,
G
1
úgy vannak választva, hogy
X
minimális legyen.
Tekintsük az
X
összes képét a
G
automorfizmusai szerint. Az
A
G
tranzitivitása miatt, ezek minden
pontot lefednek. Továbbá diszjunktak (ha különbözőek).
Mert ha
α
X
∩
β
X
≠
∅
,
α
X
≠
β
X
, akkor
α
T
-nek van közös pontja
β
X
-szel, de nem tartalmazza, ami
ellentmond 6.60(a)-nak. Ez azt is mutatja, hogy
T
az uniója az
X
bizonyos képeinek. Mivel
T
=
3
, ez csak akkor lehetséges, ha
X
=
1
(mely esetben készen vagyunk), vagy
X
=
3
.
Hogy ezt az utóbbi esetet kizárjuk, vegyük észre,
hogy
X
csak
T
-vel van összekötve. Így ha
T
=
α
X
valamely
α
-ra, akkor
T
csak
α
T
=
α
2
X
-tel van összekötve; azonban tudjuk,
hogy
T
össze van kötve
X
-szel és néhány más ponttal is (mivel
T
elvágó halmaz).
Az állítás hamis a 3 helyett 4-re, mint azt a 91.
ábra mutatja.
(b) Legyen megint
T
a
G
egy minimális elvágó halmaza, és
G
1
a
G
−
T
egy komponense, úgy választva, hogy
X
is minimális, ahol
X
=
V
G
1
. Következik, mint előbb, hogy
T
az uniója az
X
bizonyos képeinek, melyek diszjunktak,
és nem lehet, hogy
T
az
X
képe (a
G
automorfizmusai által). Ebből,
Mivel tetszőleges
x
∈
X
csak a
T
∪
X
−
{
x
}
pontjaival lehet összekötve, kapjuk,
hogy
vagy, ami ezzel ekvivalens,
Ez a becslés éles, ha
r
+
1
osztható 3-mal, mint azt egy kör és
egy teljes
r
+
1
∕
3
-gráf erős direkt szorzata mutatja
(91. ábra
r
=
5
esetén). [M. E. Watkins, J. Comb. Th.
8 (1970) 223–226;
W. Mader, Arch. d. Math.
21 (1970)
331–336.]
(c) Legyen
T
egy minimális elvágó halmaz
G
-ben, és
G
1
a
G
−
T
egy komponense. Tegyük fel, hogy
T
és
G
1
úgy vannak választva, hogy
V
G
1
minimális. Meg akarjuk mutatni, hogy
G
1
egyetlen pontból áll. Tegyük fel
indirekt módon, hogy
G
1
-nek van egy
e
éle. Legyen
f
egy, a
G
1
-et
T
-vel összekötő él, és
α
egy olyan automorfizmus, mely
f
-et
e
-re képezi le. Ekkor
α
T
metszi
G
1
-et és nem tartalmazza teljesen, ami
ellentmond 6.60(a)-nak.
- 16. feladat F Ö
Tegyük fel indirekte, hogy a
G
-beli
e
=
x
,
y
él nem fordul elő egyik 1-faktorban
sem (lehet, hogy
G
tartalmaz, de az is, hogy nem
tartalmaz 1-faktort). Ekkor
G
−
x
−
y
nem tartalmaz 1-faktort és ezért, a
Tutte tétel szerint, létezik egy
X
1
⊆
V
G
−
{
x
,
y
}
, melyre
G
−
x
−
y
−
X
1
-ben több, mint
X
1
páratlan komponens van. Paritási okok
miatt, a páratlan komponensek száma
G
−
x
−
y
−
X
1
-ben
≥
X
1
+
2
(mivel
V
G
páros). Így ha vesszük
X
=
X
1
∪
{
x
,
y
}
-t, akkor
G
−
X
-ben
≥
X
páratlan komponens van.
Legyenek
T
1
,
…
,
T
k
a
G
−
X
komponensei
k
≥
X
, és legyen
G
r
-reguláris. 12.14 szerint,
G
r
-élösszefüggő, és ezért kell, hogy
legalább
r
él kösse össze
T
i
-t
X
-szel (
i
=
1
,
…
,
k
). Ez azt jelenti, hogy legalább
k
r
él lép be
X
-be. De
X
-nek csak
X
≤
k
pontja van, hogy ezen éleket fogadja,
és
X
egy pontja legfeljebb
r
-et fogadhat. Továbbá
x
és
y
legfeljebb
r
−
1
-et fogadhat, mert
e
leköt mindkettőből egyet-egyet. Így
X
nem fogadhatja az összes
X
-be belépő élt, ami
ellentmondás.
- 17. feladat F Ö
Γ
reguláris (lásd a 11.17 megoldásához
fűzött lábjegyzetet). Legyen
x
∈
V
G
és
γ
∈
Γ
olyanok, hogy
x
,
γ
x
∈
E
G
teljesül. Ekkor
x
,
γ
x
,
…
,
γ
r
−
1
x
kört alkotnak
G
-ben (ahol
r
a
γ
rendje).
Legyen
Γ
1
a
Γ
egy maximális részcsoportja úgy, hogy
a
Γ
1
x
elemei egy
x
,
x
1
,
…
,
x
m
Γ
1
=
m
+
1
kört alkotnak. Azt állítjuk, hogy
Γ
1
x
=
V
G
, ami az állítást bizonyítja. Tegyük
fel, hogy
Γ
−
Γ
1
≠
∅
, akkor mivel
G
összefüggő, van egy olyan
a
,
b
él, melyre
a
∈
Γ
1
x
,
b
∉
Γ
1
x
. Ekkor
a
=
γ
x
γ
∈
Γ
1
és
x
,
γ
−
1
b
is szintén egy él. Világos, hogy
γ
−
1
b
∉
Γ
1
x
; legyen
γ
−
1
b
=
δ
x
,
δ
∈
Γ
−
Γ
1
. Legyen
p
a legkisebb olyan egész, melyre
δ
p
∈
Γ
1
.
A
Γ
kommutativitása miatt,
y
,
δ
y
∈
E
G
teljesül minden
y
∈
V
G
-re; valóban,
y
=
γ
x
valamely
γ
∈
Γ
-ra, és ekkor
y
,
δ
y
=
γ
x
,
δ
γ
x
=
γ
x
,
γ
δ
x
=
γ
x
,
δ
x
∈
E
G
. A kommutativitásból az is
következik, hogy
Γ
2
=
Γ
1
∪
Γ
1
δ
∪
…
∪
Γ
1
δ
p
−
1
részcsoport.
Ha
p
páros, akkor
a
Γ
2
x
pontjai által alkotott kör lesz, ami
megint csak ellentmondás (92(a) ábra). Ha
p
páratlan, akkor az
kört kapjuk, ami szintén ellentmondás (92(b) ábra).
Megjegyzés: Az a feltétel, hogy
Γ
Abel-csoport, nem hagyható el, mint
azt a Petersen gráf mutatja [J. Pelikán].
- 18. feladat F Ö
Elegendő megadni az összefüggő gráfokat, melyek a
kívánt tulajdonsággal rendelkeznek; a nem összefüggőket
úgy kapjuk, hogy tetszőleges számú összefüggő példa
diszjunkt unióját vesszük.
Két esetet különböztetünk meg. Ha
Γ
=
A
G
pont-tranzitívan hat, akkor 12.15b
szerint,
G
legalább 2-összefüggő, hacsak nem
G
=
K
2
. Továbbá, ha
G
nem 3-összefüggő, akkor 2-reguláris,
azaz, egyetlen körből áll.
Tegyük fel, hogy
G
r
-reguláris (
r
≥
3
) és 3-összefüggő. 6.69 szerint ebből
következik, hogy
G
-nek van egy lényegében egyértelmű
beágyazása a gömbre, és minden automorfizmus lapot
lapba képez le. Az él-tranzitivitás miatt, vagy minden
lap egyforma méretű, vagy csak két típusú lap van,
mondjuk
k
-szögek és
l
-szögek. Az első esetben
G
csak az öt szabályos test egyike
lehet, melynek a bizonyítása megtalálható számos
geometria könyvben.
A második esetben, az él-tranzitivitásból
következik, hogy minden él pontosan egy
k
-szöghöz és egy
l
-szöghöz illeszkedik. Így minden pont
pontosan
a
k
-szöghöz és
a
l
-szöghöz illeszkedik, valamely
a
≥
1
-re. Világos, hogy
a
≥
2
és 5.26 szerint,
E
G
=
a
⋅
n
≤
3
n
−
6
, ahonnan
a
=
2
.
Világos, hogy a
k
-szögek teljes száma
2
n
k
, és az
l
-szögeké
2
n
l
, így az Euler-formula szerint
Feltehetjük, hogy
3
≤
k
<
l
, ebből vagy
k
=
3
,
l
=
4
,
n
=
12
vagy
k
=
3
,
l
=
5
,
n
=
30
. Könnyű látni, hogy a megfelelő
gráfok a kocka, ill. a dodekaéder élgráfjai.
Most tegyük fel, hogy
Γ
nem tranzitív a pontokon. Ekkor
világos, hogy
A
G
-nek két tranzitivitási osztálya van
V
G
-n, mondjuk
U
és
W
. Minden él két különböző osztályba
tartozó pontot köt össze.
Ha
G
-ben a minimális fokszám 1, akkor egy
csillagot kapunk. Ha a
G
-beli minimális fokszám 2, akkor ez
úgy keletkezik, hogy egy (nem szükségképpen egyszerű),
síkbarajzolható
G
1
gráf minden élére még egy pontot
teszünk. Ennek a
G
1
gráfnak az automorfizmuscsoportja
tranzitív mind a pontokon, mind az éleken. Ebből
következik, hogy
G
1
a fent meghatározott élekből úgy
keletkezik, hogy minden élét ugyanazzal a számmal
megtöbbszörözzük. Így
G
egyike azon gráfoknak, melyeket az
ötlettárban adtunk meg.
Így tegyük fel, hogy a minimális fokszám
G
-ben legalább 3. Ekkor
G
3-összefüggő 12.15c szerint, és így
6.69 szerint lényegében egyértelműen ágyazható be a
gömbbe. Az él-tranzitivitásból ismét következik, hogy
A
G
vagy tranzitív a lapokon, vagy
kétfajta lap van. Az első esetben tekintsük a duális
gráfot,
G
∗
-ot. Ennek az automorfizmuscsoportja
tranzitív mind a pontokon, mind az éleken, és így
egyike a fentebb már meghatározott gráfoknak.
Így feltehetjük, hogy
A
G
nem tranzitív a lapokon sem. Legyen
mindegyik él egy
k
-szögű és egy
l
-szögű lap határán. Legyen az
U
-beli pontok foka
a
, a
W
-beli pontok foka
b
. Mivel az egy adott pontot tartalmazó
lapok felváltva tartoznak a két tranzitivitási
osztályba,
a
és
b
páros, így egyik sem lehet 4-nél
kisebb. Hasonlóan
k
,
l
≥
4
. De ekkor a pontok száma legfeljebb
E
G
∕
2
, a lapok száma legfeljebb
E
G
∕
2
, ami ellentmond az Euler tételnek.
Így az utóbbi eset nem fordulhat elő. Ezzel az
ötlettárban megadott lista teljességét
bebizonyítottuk.
- 19. feladat F Ö
Legyen
Γ
egy nem ciklikus egyszerű csoport, és
tegyük fel, hogy
A
G
≅
Γ
, ahol
G
síkbarajzolható gráf. Megmutatjuk,
hogy ebből következik, hogy
Γ
≅
A
5
, még abban az esetben is, ha meg van
engedve a pontok színezése. Legyen
G
minimális azon gráfok között, melyekre
A
G
≅
Γ
. Ekkor
G
összefüggő. Mert tegyük fel, hogy
G
komponensei a
G
1
,
…
,
G
k
gráfok. Ekkor a
G
minden automorfizmusa a komponensek
egy permutációját indukálja. Azok az automorfizmusok,
melyek az identitást indukálják, az
A
G
egy normálosztóját alkotják. Mivel
A
G
egyszerű, ezért vagy nincs olyan
automorfizmus, mely az identitást indukálja, vagy
mindegyik ilyen. Az első esetben a
G
komponensei aszimmetrikusak és így
A
G
szimmetrikus csoportok direkt szorzata
(melyek permutálják az izomorf komponenseket), és így
sohasem lesz egy nem ciklikus egyszerű csoport. Így
mindegyik automorfizmus a komponenseket invariánsan
hagyja. Legyen
G
1
egy olyan komponens, mely nem
aszimmetrikus, akkor azok az automorfizmusok, melyek a
G
1
pontjait fixen hagyják, az
A
G
-nek egy valódi normálosztóját
alkotják. Mivel
A
G
egyszerű, ebből következik, hogy csak
az identitás ilyen, azaz,
A
G
≅
A
G
1
, ami ellentmond a
G
minimalitásának.
Jegyezzük meg továbbá, hogy
A
G
-nek nincsenek fixpontjai. Mert
elhagyva egy fixpontot, és a szomszédait egy új színnel
kiszínezve, egy kisebb színezett gráfot kapunk, melynek
ugyanaz az automorfizmus csoportja.
Húzzuk össze a
G
egy megfelelő összefüggő részgráfját
G
0
-ra, úgy hogy
A
G
0
tartalmaz egy
Γ
′
≅
A
G
részcsoportot, mely él-tranzitívan hat
(12.12b-hez hasonlóan). Vegyük észre, hogy ez a
konstrukció 12.12b-ben olyan, hogy ha
A
G
-nek nincs fixpontja, akkor
Γ
′
-nek sincs.
G
0
nyilvánvalóan síkbarajzolható, így
egyike azoknak a gráfoknak, melyeket a megelőző
ötletben írtunk le. A csillagokat kizárja az, hogy
Γ
′
-nek nincs fixpontja. A megmaradó
példák a szabályos testek, vagy gráfok, melyeknél
könnyen látható, hogy ugyanaz az
automorfizmuscsoportjuk, mint a szabályos testeknek.
Felhasználva 12.2-t, könnyű látni, hogy az
automorfizmuscsoportok, az
A
5
-től különböző nem ciklikus egyszerű
csoportot nem tartalmaznak.
Megjegyzés:
A 93. ábra egy olyan síkbarajzolható
gráfot mutat, melynek az automorfizmuscsoportja
A
5
. [L. Babai, in: Infinite and
Finite Sets, Coll. Math. Soc. J. Bolyai
10
Bolyai–North-Holland (1975) 29–84.]
- 20. feladat F Ö
(a) Felhasználva 12.12a-t, feltehetjük, hogy
Γ
regulárisan hat. Ekkor könnyű látni,
hogy
G
′
tartalmazza két
p
−
1
hosszúságú út és egy él
Descartes-szorzatát. (Valójában tartalmazza három
p
hosszúságú kör Descartes-szorzatát.)
Legyen
G
⊃
P
⊕
P
′
⊕
Q
,
P
=
x
1
,
…
,
x
p
,
P
′
=
y
1
,
…
,
y
p
,
Q
=
z
1
,
z
2
. Elegendő megmutatni, hogy
P
⊕
P
′
⊕
Q
összehúzható
K
p
-re. Ennek befejezésére, húzzuk össze
a
P
⊕
{
y
i
}
⊕
{
z
1
}
és a
{
x
i
}
⊕
P
′
⊕
{
z
2
}
által kifeszített részgráfokat
(amelyek nyilvánvalóan összefüggőek). Ennek
eredményeként egy a
K
p
,
p
-vel izomorf gráfot kapunk, ami
triviális, hogy összehúzható
K
p
-re (94. ábra).
(b) Az előző probléma megoldásához hasonlóan,
feltehetjük, hogy a
Γ
′
hatása él-tranzitív. (a) szerint
feltehetjük, hogy
Γ
hatása nem félig reguláris. Tegyük
fel, hogy
γ
0
∈
Γ
-nak van fixpontja. Mivel
G
összefüggő, van neki két összekötött
x
0
,
y
0
pontja úgy, hogy
γ
0
x
0
=
x
0
, de
γ
0
y
0
≠
y
0
. Ekkor
y
0
,
γ
0
y
0
,
…
,
γ
p
−
1
y
0
az
x
0
-nak különböző szomszédai. Ebből
d
G
x
0
≥
p
.
Ha
A
G
pont-tranzitív, akkor minden pont foka
legalább
p
, és készen vagyunk Mader tételét
használva (10.8 feladat). Így tegyük fel, hogy
A
G
nem pont-tranzitív. Az
él-tranzitivitás miatt következik, hogy
Γ
′
-nek két tranzitivitási osztálya van,
nevezetesen
U
=
Γ
′
x
0
és
W
=
Γ
′
y
0
. Mindegyik él
U
-ból
W
-be megy. Triviális, hogy minden
U
-beli fok legalább
p
és minden
W
-beli legalább 2. Ha
W
-ben a fokok legalább
p
3
nagyságúak, még mindig befejezhetjük a
bizonyítást 10.8-at használva. Így tegyük fel, hogy a
W
-beli fokok kisebbek, mint
p
3
.
Alkossunk egy
G
1
gráfot a
V
G
1
=
U
-n úgy, hogy két pontot akkor kötünk
össze, ha a távolságuk
G
-ben 2. Minden
γ
∈
Γ
′
indukál egy
γ
¯
∈
A
G
1
-t. Világos, hogy
γ
↦
γ
′
egy homomorfizmus, és mivel
Γ
′
egyszerű, ezért vagy egy
monomorfizmus, vagy mindent az 1-re képez le. Azonban
az utóbbi lehetetlen, mert
Γ
′
tranzitívan hat
U
-n. Továbbá,
γ
0
-nak vannak fixpontjai, de nem az
identitás, így az előzőekhez hasonlóan következik, hogy
minden
G
1
-beli legalább
p
.
Minden
e
=
u
,
v
∈
E
G
1
élre, legyen
f
e
az
u
,
v
G
-beli közös szomszédainak egyike.
Világos, hogy
f
e
∈
V
. Egy
y
∈
V
pont legfeljebb
féleképpen fordul elő, mint
f
e
e
∈
E
G
1
és így, az
f
e
alakú pontok száma legalább
Minden
f
e
alakú
x
ponthoz válasszunk egy olyan
u
x
,
v
x
=
e
x
∈
E
G
1
élet, melyre
f
e
x
=
x
, és húzzuk össze az
u
x
,
x
élet
G
-ben. Azonosítsuk a
W
azon pontjait, amelyek nem
f
e
alakúak, egy tetszőleges
szomszédjukkal. Ezen a módon
G
le van képezve
G
1
-nek egy
G
′
részgráfjára, mely az összes
e
x
alakú élt tartalmazza (és lehet, hogy
még többet). Így
Így a 10.8 szerint
G
′
összehúzható
K
m
-re.
(c) Legyen
N
egy elég nagy szám; megmutatjuk, hogy
az
A
N
alternáló csoport nem izomorf egyetlen
K
-beli gráf automorfizmuscsoportjával
sem, még akkor sem, ha számításba vesszük pontok
színezését is. Pontosabban megmutatjuk, hogy ha egy
G
gráf (melynek esetleg színezettek a
pontjai) automorfizmuscsoportja
A
N
, akkor ennek egy alkalmas részgráfja
kontrahálható
K
m
-re, feltéve, hogy
N
≥
3
p
, ahol
p
egy prím, és
p
>
8
m
. Mivel elég nagy
m
-re
K
bizonyosan nem tartalmaz egyetlen
gráfot sem, mely kontrahálható
K
m
-re, ez már bizonyítani fogja az
állítást.
A 12.19 megoldásához hasonlóan feltehetjük, hogy
G
összefüggő, és
A
G
-nek nincs fixpontja. Ekkor elfelejtve
a pontok színezését, egy olyan gráfhoz jutunk, mely
kielégíti a (b) feltételeit. Ebből következik, hogy
G
kontrahálható
K
m
-re. [L. Babai, Discrete Math.
8
(1974) 13–20.]
- 21. feladat F Ö
Legyen
G
egy gráf, melyre
A
G
≅
Γ
,
V
G
∩
Ω
=
∅
. A 12.5-beli konstrukció alapján
feltehetjük, hogy
A
G
félig regulárisan hat a
G
-n, azaz nincs olyan
α
≠
1
elem, melynek van fixpontja.
A 12.5-beli konstrukció alapján azt is
feltehetjük hogy
V
G
≥
Γ
⋅
Ω
; ekkor
A
G
-nek legalább
Ω
pályája van
V
G
-n. Végül a 12.5-beli konstrukció
komplementerét véve, elérhetjük, hogy minden
G
-beli fokszám nagyobb legyen, mint
Γ
. Legyen
γ
↦
γ
a
Γ
egy izomorfizmusa
A
G
-vel. Legyenek
Ω
1
,
…
,
Ω
k
a
Γ
pályái
Ω
-n és válasszunk egy
y
i
∈
Ω
i
-t
i
=
1
,
…
,
k
. Legyenek
x
1
,
…
,
x
k
∈
V
G
pontok különböző pályákon. Minden
γ
∈
Γ
és
1
≤
i
≤
k
esetén, kössük össze
γ
y
i
-t
γ
¯
x
i
-vel. Az eredményül kapott
G
′
gráfon a
γ
′
permutációk mint automorfizmusok
hatnak, ahol
Világos ugyanis, hogy
γ
′
megőrzi a
V
G
-beli éleket, és ha
γ
0
y
i
,
γ
¯
x
i
egy tetszőleges új él, akkor
γ
′
γ
0
y
i
,
γ
¯
x
i
=
γ
0
γ
y
i
,
γ
0
γ
¯
x
i
is egy új él lesz.
Másrészt,
G
′
-nek nincs más automorfizmusa. Legyen
α
∈
A
G
′
. Ekkor
α
megőrzi
V
G
-t, mint az olyan pontok halmazát,
melyeknek a foka nagyobb, mint
Γ
. Ezért
α
|
v
G
=
γ
¯
|
V
G
valamely
γ
∈
Γ
-ra. Legyen
y
∈
Ω
, ekkor
y
=
δ
y
i
valamely
δ
∈
Γ
-ra, és
1
≤
i
≤
k
. Mivel
α
egy izomorfizmus,
α
y
össze van kötve
α
δ
¯
x
i
=
δ
γ
¯
x
i
-vel. De az egyetlen olyan pont
Ω
-ban, mely össze van kötve
δ
γ
¯
x
i
-vel,
δ
γ
y
i
. Így
α
y
=
δ
γ
y
i
=
γ
y
. Így ahhoz jutunk, hogy
α
=
γ
′
.
Ez bizonyítja, hogy
G
′
-nek megvan a kívánt tulajdonsága. [I.
Z. Bouwer, J. Comb. Th.
6 (1969) 378–386; Z. Hedrlin–A.
Pultr, Illinois J. Math.
10 (1966) 392–405.]
- 22. feladat F Ö
Az ötlettárbeli állítás könnyen következik két
észrevételből:
(a) Ha
η
egy tetszőleges endomorfizmusa a
Petersen gráfnak, és
C
egy ötszög a Petersen gráfban, akkor
η
egy-egyértelmű a
C
-n.
C
képe nem színezhető ki 2 színnel, mert
tartalmaz egy páratlan kört (ez nem színezhető ki 2
színnel, mert ez a
C
egy 2-színezését adná); a legrövidebb
páratlan kör a Petersen gráfban az ötszög. Így
η
C
tartalmaz egy ötszöget és így
η
egy-egyértelmű a
C
-n.
(b) A Petersen gráf tetszőleges két pontja benne
van egy ötszögben.
Ezért nincs olyan endomorfizmus, mely két
különböző pontot azonosítana. Így, az endomorfizmus
félcsoport
≅
S
5
12.1 szerint.
- 23. feladat F Ö
Tekintsük a 95. ábrán látható gráfot, ahol
s
>
a
+
b
+
c
páratlan. Ez a
G
gráf három
s
hosszúságú kört tartalmaz, és egy
3
s
−
2
a
+
b
+
c
>
s
hosszúságút. Ezért, a
G
tetszőleges
η
endomorfizmusa egy-egyértelmű kell,
hogy legyen az
s
hosszúságú körökön. Továbbá,
x
három szomszédja páronként az
s
hosszúságú körökön fekszik, így
η
x
-nek három különböző szomszédja kell,
hogy legyen, melyek szintén páronként ilyen körökön
fekszenek. Ebből következik, hogy
η
x
=
x
. Triviálisan következik, hogy ha
a
,
b
,
c
különbözőek, akkor
η
-nak a három „küllőt” fixen kell
hagynia. Az
s
−
a
−
c
hosszúságú ív az „abroncson” nem
képezhető le semelyik másik ívre, melynek ugyanezek a
végpontjai, mert csak két másik ugyanolyan paritású út
van, nevezetesen a
c
+
b
+
s
−
a
−
b
és a
a
+
b
+
s
−
b
−
c
hosszúságúak, de ezek hosszabbak. Így
η
=
1
. [Z. Hedrlin–A. Pultr, Monatsh. f.
Math. 69
(1965) 318–322.]
- 24. feladat F Ö
(a) Legyenek
η
1
,
…
,
η
n
a
Σ
elemei. Tekintsük ezeket egy színezett
irányított
G
gráf pontjainak. Kössük össze
η
i
-t
η
j
-vel egy irányított,
k
színű éllel, ha
η
i
=
η
k
η
j
. Mivel csak egy félcsoportunk van,
megtörténhet, hogy bizonyos párok több, különböző színű
éllel vannak össze kötve, mások meg egyáltalán
nincsenek összekötve.
Tetszőleges
η
m
-re, alkalmazva a
η
¯
m
η
j
=
η
j
η
m
definiáló egyenlőséget, a
G
-nek egy endomorfizmusát kapjuk; mert
ha egy
k
színű él köti össze
η
i
-t
η
j
-vel, azaz,
η
i
=
η
k
η
j
, akkor
η
i
η
m
=
η
k
η
j
η
m
, azaz, egy
k
színű él köti össze
η
¯
m
η
i
-t
η
¯
m
η
j
-vel. Továbbá, az
η
¯
m
-ek a
G
-nek különböző endomorfizmusai; mert
ha
η
¯
m
η
i
=
η
¯
l
η
i
minden
i
-re, akkor biztos, hogy,
η
¯
m
1
=
η
¯
l
1
, azaz,
m
=
l
.
Azt állítjuk, hogy
G
-nek nincs más endomorfizmusa. Legyen
ɛ
∈
E
n
d
G
és tekintsük
η
m
=
ɛ
1
-t. Azt állítjuk, hogy
ɛ
=
η
¯
m
. Legyen
η
i
∈
V
G
. Ekkor
η
i
egy
i
színű éllel van összekötve 1-gyel,
mert
η
i
=
η
i
⋅
1
. Ezért
ɛ
η
i
i
színű éllel van összekötve
ɛ
1
=
η
m
-mel, mivel
ɛ
egy endomorfizmus. Ebből
(b) Először vegyük észre, hogy tetszőlegesen sok
egyszerű gráf létezik, melyek merevek, és nincs olyan
homomorfizmus, mely egymásba vinné őket. Vegyünk egy
elég nagy
s
-et, és különféleképpen megválasztott
a
,
b
,
c
-t úgy, hogy
a
+
b
+
c
=
s
−
1
teljesüljön a 12.20 megoldásában
megadott konstrukcióban. Legyenek
G
1
,
…
,
G
N
ezek a merev gráfok, ahol
N
=
2
Σ
. Minden
G
i
minden pontja benne van egy
s
hosszúságú páratlan körben, mely a
legrövidebb mindegyikben.
Helyettesítsük az (a) részben megkonstruált
G
gráf minden
k
színű
x
,
y
élét egy lánccal, ahogy a 96. ábrán
látható. Az a két él, amelyikkel a
G
i
-hez csatlakozik, mindegyik esetben
ugyanarra a két pontra illeszkedik. A hurkokat
hasonlóan helyettesítjük.
Az eredményül kapott
G
′
gráfnak világos, hogy vannak
endomorfizmusai, mindegyik
G
-beli
η
¯
i
endomorfizmusnak megfelel egy
η
˜
i
endomorfizmus. Azt állítjuk, hogy
nincs más endomorfizmusa. Mivel
G
′
-nek nincs másik
s
hosszúságú köre, vagy rövidebb köre a
G
i
-belieken kívül, következik, hogy
tetszőleges
ɛ
∈
End
G
a
G
i
pontjait a
G
i
pontjaira képezi le. Mivel ezek
merevek, és nem képezhetők le egymásba, következik,
hogy
ɛ
mindegyik
G
i
-t ugyanannak a gráfnak egy példányába
képezi le. A
G
pontjai különböző
G
i
-beli pontokkal vannak összekötve.
Ezért
ɛ
V
G
⊆
V
G
. Azt is könnyű látni, hogy ha
x
és
y
össze vannak kötve
G
-ben egy
k
színű éllel, azaz, a
G
′
-ben
G
2
k
−
1
-esek és
G
2
k
-esek egy láncával vannak összekötve
(lásd a 96. ábrát), akkor
ɛ
x
és
ɛ
y
is össze van kötve, és egyetlen olyan
leképezés létezik, mely az
x
,
y
-láncot az
ɛ
x
,
ɛ
y
-láncra képezi le. Ezért,
ɛ
=
η
˜
i
teljesül valamely
i
-re. [Z. Hedrlin–A. Pultr, Monatsh. f.
Math. 68 (1964) 213–217;
lásd még Z. Hedrlin–J. Lambek,
J. of Alg. 11
(1969) 195–212.]
- 25. feladat F Ö
(a) Tegyük fel, hogy
End
G
=
{
1
,
α
,
ω
}
, ahol
ω
egy 0-elem:
α
ω
=
ω
α
=
ω
, 1 az identitás, és
α
2
=
1
. Hagyjuk el az
e
=
x
,
y
élt. Ha
ω
nem marad endomorfizmus, akkor létezik
egy olyan
x
1
,
y
1
∈
E
G
−
e
él, melyre
ω
x
1
=
x
,
ω
y
1
=
y
. Hasonlóan, ha
α
nem marad endomorfizmus, akkor létezik
egy olyan
x
2
,
y
2
∈
E
G
−
e
él, melyre
α
x
2
=
x
,
α
y
2
=
y
. De ekkor
ami azt jelenti, hogy
x
2
,
y
2
nem egy éle
G
−
x
,
y
-nak, ami ellentmondás.
(b) Tekintsük a 12.21.(b) megoldásában leírt
konstrukciót, de válasszuk
s
-et úgy, hogy legyen még egy merev
G
N
+
1
gráfunk, melynek a derékbősége
s
, és nincs endomorfizmusa
G
1
,
…
,
G
N
-be, és megfordítva. Ha
G
N
+
1
-et, mint egy új komponenst adjuk
hozzá a
G
′
-hez, akkor egy
G
″
gráfot kapunk, melyre
End
G
″
≅
End
G
′
≅
Σ
. Azonban, ha összekötjük a
V
G
egy pontját
G
N
+
1
-gyel egy éllel, az eredményül kapott
gráf merev lesz.
[L. Babai–J. Nešetřil.]