2. FEJEZET: A skatulyaelv gráfelméleti élesítései, II.
,,TURÁN-TÍPUSÚ" TÉTELEK
Ez a típus az
1.5. feladatban részben - páros pontszámra - már bizonyított tételről nyerte nevét. (A minden gráfra érvényes tétel bizonyítását l. a
K.II.12.17. feladatban, illetve a
2.3. feladatban.) Maga a kérdés és a rá adott válasz is Turán Páltól származik. Általános megfogalmazásban azt kérdezzük, hogy egy
n pontú gráfban hány él kell ahhoz, hogy egy bizonyos meghatározott gráffal izomorf részgráf (az eredeti problémában: háromszög) biztosan legyen benne. Pontosan a következőképp fogalmazhatunk:
Legyen
G egy tetszőleges véges gráf. Jelölje
eG
(n) azt a legnagyobb
e számot, amelyre igaz, hogy van olyan
n pontú,
e élű egyszerű gráf, amelyben nincs
G-vel izomorf részgráf. (Tehát minden
n pontú,
eG
(n)+1 élű egyszerű gráfban már van
G-vel izomorf részgráf.) A későbbiekben a kétszeres indexelés elkerülése érdekében
e
Ck
(n)-et egyszerűen
ek
(n)-nel fogjuk jelölni.
Azokat az
n pontú,
eG
(n) élű gráfokat, amelyekben nincs
G-vel izomorf részgráf,
extremális gráfoknak nevezzük.
Ilyen típusú egyszerű kérdéseket foglal össze a
2.1. feladat.
Itt is egy bonyolultabb formájú skatulyaelvvel állunk szemben. Kétszeresen is. A skatulyaelv pusztán ,,mennyiségi" formájában azt mondja ki, hogy ha elég sok objektumom van és beosztom aránylag kevés csoportba őket, akkor az egyik csoportban jó sok lesz. Már a Ramsey-típusú tételeknél sem elégszünk meg azzal, hogy jó sok legyen valamiből (élből), hanem ezeknek az egymáshoz való viszonyáról, struktúrájáról is tudni akarunk valamit. Ezeknél tehát már valamivel minőségibb, ,,strukturált skatulyaelvről" van szó. Most viszont még egy élesítést bevezetünk: nem
minden él közül válogathatunk, hanem egy bizonyos struktúrájú gráf élei között.
Egy nagyon egyszerű ilyen típusú állítás a
K.II.12.5. feladat állítása: eszerint ha egy egyszerű véges gráfban minden pont foka legalább kettő, akkor van benne kör. De azt ennyiből még nem tudhatjuk, hogy pontosan milyen hosszú kört tudunk garantálni. A legkézenfekvőbb kérdés - és ez volt Turán kérdése - így szól: milyen feltétel mellett tudjuk garantálni, hogy legyen háromszög a gráfban?
Turán tétele
Feladat: 2.1. Állapítsuk meg
eG
(n) értékét, ha
a)
G a
k pontú csillag (feltesszük, hogy
n(k-1) páros);
b)
G
k független élből áll,
k=1,2;
c)
G
n pontú kör.
Feladat: 2.2. Mutassunk példát olyan gráfra, amelyben
a) minden pont foka legalább három, mégsincs benne három hosszú kör.
b) amelyben minden pont foka legalább három, mégsincs benne sem három, sem négy hosszú kör.
c) amelyben minden pont foka legalább
⌊n/2⌋ (ahol
n a gráf pontszáma), mégsincs benne három hosszú kör.
Megmaradt tehát a kérdés: mit kell megkövetelnünk a legkisebb fokszámról ahhoz, hogy biztosan legyen a gráfban háromszög? A fenti (2.2.) feladat c) része mutatja, hogy ,,nagyon sokat". De vajon elég-e ez? Az 1.9. feladat erre ad választ: ha azt kérdezzük, hogy mit kell feltennünk a legkisebb fokszámról ahhoz, hogy biztosan legyen a gráfban háromszög, akkor több, mint a pontszám fele kell: legalább
⌈(n+1)/2⌉.
Vajon nem jutunk-e jobb eredményhez, ha nem a
minimális fokszámra teszünk kikötést, hanem csak az
átlagfokszámra, vagy ami ugyanaz: az élszámra? Hiszen elképzelhető, hogy így erősebb tételhez jutunk. Erre is láttunk már példát: láttuk, hogy ha minden pont foka legalább kettő, akkor van kör a gráfban. De azt is láttuk, hogy ennél kevesebb is elég. A
K.II.7.4. feladat azt mondja, hogy elég, hogy ha az
átlagfokszám 2 - vagyis az élszám legalább annyi, mint a fokszám -, már akkor is van kör a gráfban. (Végig egyszerű gráfokról van szó.)
A következő (
2.3.) feladat háromszögre mond ki hasonlót.
Feladat: 2.3. Bizonyítsuk be Turán Pál következő tételét:
Tétel. Ha egy
n pontú egyszerű gráfban több, mint
⌊
n2
/4⌋ él van (azaz az átlagfokszám nagyobb
n/2-nél), akkor van benne háromszög.
A becslés pontos: van (izomorfia erejéig pontosan egy) olyan
n pontú,
⌊
n2
/4⌋ élű egyszerű gráf, amelyben nincs háromszög.
Vagyis a bevezetett jelöléssel:
e3
(n)=⌊
n2
/4⌋.
Feladat: 2.4. Bizonyítsuk be a
2.3. feladat állítását páratlan pontszám esetén az
1.5. feladat megoldásának gondolatmenetével!
Feladat: 2.5. * a) Bizonyítsuk be, hogy ha
n>1 és egy
2n pontú egyszerű gráfban több, mint
n2
él van, akkor van benne négy olyan pont, amelyek között legalább öt él fut. [
180]
b) Bizonyítsuk be, hogy
n2
él esetén a) állítás már nem mindig igaz: van olyan
n pontú,
n2
élű egyszerű gráf, amelyben bármely négy pont között legfeljebb négy él fut.
Tehát
eG
(2n)=
n2
, ahol
G a négypontú, ötélű gráf.
Feladat: 2.6. Fogalmazzuk meg, hogy mi köze van a háromszögekre vonatkozó Turán-tételnek (
2.3. feladat) a következő kérdéshez:
Legalább hány éle van annak az
n pontú egyszerű gráfnak, amelyben nincs három független pont (vagyis bármely három pontja között van kettő, amelyik össze van kötve)?
Megjegyzés. A következő (=
2.7.-
2.10.) feladatok ezzel a kérdéssel foglalkoznak. Érdemes azt is meggondolni, hogy az itt kapott bizonyításnak mi a köze a Turán-tételre a
2.3. feladatban adott bizonyításhoz.
Feladat: 2.7. a) Mit tudunk mondani a maximális fokszámról egy olyan hétpontú gráfban, amelynek legalább nyolc éle van?
b) Mit tudunk mondani a maximális fokszámról egy olyan kilencpontú egyszerű gráfban, amelynek 14 éle van?
Feladat: 2.8. Legalább hány éle van egy olyan
n pontú egyszerű gráfnak, amelyben bármely három pont közül legalább kettő össze van kötve, ha
n=4,5,6,7,8 vagy
9?
A feladat kérdését úgy is megfogalmazhatjuk, hogy minimálisan hány éle van egy olyan
n pontú gráfnak, amelyben nincs három független pont?
Feladat: 2.9. Egy
n pontú egyszerű gráfban nincs független ponthármas (vagyis bármely három pont közül van kettő, amelyik össze van kötve). Mit tudunk mondani a gráf maximális fokszámáról?
Feladat: 2.10. Minimálisan hány éle lehet egy olyan
n pontú egyszerű gráfnak, amelyben nincs három független pont (azaz bármely három pontja közül legalább kettő között fut él)?
Megjegyzés. Turán Pál a tételét általánosabban is felállította. Általánosan az a kérdés, hogy legfeljebb hány éle van egy olyan gráfnak, amelyben nincs teljes
k-as (
k pontú teljes részgráf). Vagy a komplementerre átfogalmazva: legalább hány éle van egy olyan gráfnak, amelyben nincs
k független pont? Ez utóbbi kérdésre adnak választ a
2.11-
2.12. feladatok.
Feladat: 2.11. a) Egy
3k+1 pontú egyszerű gráfban nincs független pontnégyes. Legalább mekkora a legmagasabb fokú pont fokszáma?
b) Egy
mk+1 pontú egyszerű gráfban nincs
m+1 darab független pont. Legalább mekkora a legmagasabb fokú pont fokszáma?
Feladat: 2.12. Minimálisan hány éle lehet egy olyan
n pontú egyszerű gráfnak, amelyben nincs négy független pont (azaz bármely négy pontja közül legalább kettő között fut él)?
Feladat: 2.13. Fogalmazzuk át a
2.12. feladat a) részének eredményét arra az esetre, ha azt kérdezzük: maximálisan hány éle lehet egy
3n pontú egyszerű gráfnak, ha nincs benne négypontú teljes gráf? Vagyis határozzuk meg
e
K4
(n) értékét.
Feladat: 2.14. Legyen
n>4. Egy
n pontú egyszerű gráfban bármely öt pont között legalább két él fut. Minimálisan hány éle van a gráfnak?
Néhány geometriai alkalmazás
Feladat: 2.15. * Adott egy kör kerületén 100 pont. Két pont ,,távolságán" a kör kerületén vett távolságát, azaz a két pont által határolt két ív közül a kisebbik hosszát értjük. (Átmérő esetén a távolság a félkörív.) Bizonyítsuk be, hogy a 100 pont között fellépő távolságok közül legfeljebb 2500 lehet a kör kerületének harmadánál nagyobb.
Feladat: 2.16. a) Adott a síkon öt pont, bármely kettő távolsága legfeljebb egységnyi. Bizonyítsuk be, hogy a köztük fellépő tíz távolság közül legalább kettő kisebb, mint
1/2.
b) Adott a síkon hat pont, bármely kettő távolsága legfeljebb egységnyi. Bizonyítsuk be, hogy a köztük fellépő 15 távolság közül legalább három kisebb, mint
1/2.
c) Adott a síkon hét pont, bármely kettő távolsága legfeljebb egységnyi. Bizonyítsuk be, hogy a köztük fellépő 21 távolság közül legalább öt kisebb, mint
1/2.
d) Adott a síkon kilenc pont, bármely kettő távolsága legfeljebb egységnyi. Bizonyítsuk be, hogy a köztük fellépő 36 távolság közül legalább kilenc kisebb, mint
1/2.
Feladat: 2.17. Adott a síkon
3n pont (
n>1) úgy, hogy bármely két pont távolsága legfeljebb egységnyi. Bizonyítsuk be, hogy a
3n pont között fellépő
3n(3n-1)/2 távolság közül legfeljebb
3
n2
van, amely nagyobb, mint
1/2. [
180]
,,Turán-típusú" tételek körökre
A háromszögekre vonatkozó Turán-tételnek létezik azonban másféle általánosítása is. A három pontú teljes gráf egyben három hosszú kör is. Vajon milyen feltétel mellett van például négy hosszú kör a gráfban? A
K.II.12.10. feladat szerint ha minden pont foka legalább három, akkor már van benne
legalább négy hosszú kör. De mi
pontosan négy hosszú kört keresünk, és ez már sokkal fogasabb kérdés. A
2.19-
2.21. feladatok ezt a kérdést járják körül. Előbb azonban egy valamivel egyszerűbben eldönthető esettel foglalkozunk:
e5
(n) meghatározásával. Érdekes módon ugyanis könnyebb megmondani, hány él kell ahhoz, hogy legyen ötpontú kör a gráfban, mint azt, hogy hány él kell ahhoz, hogy legyen benne négypontú kör. Az egyszerűség kedvéért a páros pontszám esetére szorítkozunk.
Feladat: 2.18. * Bizonyítsuk be, hogy ha
k>2 és egy
n=2k egyszerű gráfban legalább
k2
+1 él van, akkor van benne
C5
. Mutassunk példát olyan
2k pontú,
k2
élű gráfra, amelyben nincs
C5
.
Képlettel kifejezve a feladat azt mondja, hogy
e5
(2k)=
e3
(2k)=
k2
.
Feladat: 2.19. Nyilvánvaló, hogy ha egy négypontú egyszerű gráfban legalább öt él van, akkor van benne négy hosszú kör. És - izomorfiától eltekintve - egyetlen olyan négypontú, négyélű gráf van, amelyben nincs négy hosszú kör: ez egy (háromágú) csillag, amelynek két végpontja még össze van kötve.
Bizonyítsuk be, hogy
a) ha egy ötpontú egyszerű gráfban legalább hét él van,
b) ha egy hatpontú egyszerű gráfban legalább nyolc él van,
c) ha egy hétpontú egyszerű gráfban legalább kilenc él van,
akkor van benne
C4
(azaz négy hosszú kör), de kevesebb él esetén ez nem mindig igaz.
Vagyis bizonyítandó, hogy
|
e4
(4)=4,
e4
(5)=6,
e4
(6)=7,
e4
(7)=9.
|
Az általános tételt ld. a
2.21. és a
2.29 feladatban.
Feladat: 2.20. a) Bizonyítsuk be, hogy ha egy
n pontú egyszerű gráfban nincs
C4
, és egy
x pontjának a foka
d, akkor az
x-szel összekötött pontokból induló élek száma legfeljebb
n-1+⌊d/2⌋.
Bizonyítsuk be, hogy
b)
e4
(8)=11, azaz ha egy nyolcpontú egyszerű gráfban legalább 12 él van, akkor van benne
C4
, de ugyanez nem minden 11 élű (nyolcpontú egyszerű) gráfra igaz.
c) Bizonyítsuk be, hogy
e4
(9)=13, azaz ha egy kilencpontú egyszerű gráfban legalább 14 él van, akkor van benne
C4
, de ugyanez nem minden 13 élű gráfra igaz.
Feladat: 2.21. a) Bizonyítsuk be, hogy ha egy
n pontú gráfban nincs
C4
és van egy
d-edfokú pontja, akkor élszáma legfeljebb
n-1+⌊d/2⌋+
e4
(n-1-d).
b) Bizonyítsuk be, hogy
e4
(n)≤n-1+⌊d⌋+
e4
(n-1-2d) valamely
d≥2
e4
(n)/n egész számra.
c) Próbáljuk c) alapján felső becslést adni
e4
(n)-re.
Feladat: 2.22. a) Bizonyítsuk be, hogy egy gráfban pontosan akkor nincs négypontú kör (
C4
), ha semelyik két pontnak nincs két közös szomszédja.
b) Mutassuk meg, hogy ha van egy 15 pontú 4-reguláris gráf, amely nem tartalmaz
C4
-et, akkor igaz a következő: ha
H egy 15-elemű halmaz, akkor a
H halmaznak megadható 15 olyan négyelemű részhalmaza, amelyek közül bármely kettőnek legfeljebb egy közös eleme van.
Feladat: 2.23. a) Mutassuk meg, hogy minden 12 pontú, 4-reguláris egyszerű gráf tartalmaz
C4
-et.
b) Tudjuk, hogy van egy
n pontú,
k reguláris egyszerű gráf, amelyben nincs
C4
és legyen
H egy
n elemű halmaz. Bizonyítsuk be, hogy megadható a
H halmaznak
n darab
k elemű részhalmaza úgy, hogy bármely kettőnek legfeljebb egy közös eleme van.
Feladat: 2.24. Mutassuk meg, hogy a
2.23. feladatban használt gondolatmenet ,,egyirányú", az ottani b) állítás megfordítása nem igaz: abból, hogy egy
n elemű halmaznak megadható
n darab
k elemű részhalmaza úgy, hogy közülük bármely kettőnek legfeljebb egy közös eleme van, még nem következik, hogy van olyan
n pontú
k-reguláris gráf, amelyben nincs
C4
.
Feladat: 2.25. Bizonyítsuk be, hogy ha egy húszpontú egyszerű gráf nem tartalmaz
C4
-et, akkor van egy legfeljebb negyedfokú pontja. Vagy másképp: ha egy húszpontú egyszerű gráf minden pontja legalább ötödfokú, akkor tartalmaz
C4
-et.
Feladat: 2.26. a) Legyen
G egy
n2
pontú,
n+1-reguláris gráf. Bizonyítsuk be, hogy
G tartalmaz
C4
-et.
b) Igaz-e az állítás akkor is, ha csak azt tudjuk, hogy minden pont legalább
n+1-ed fokú?
Feladat: 2.27. a) Most azt akarjuk bebizonyítani, hogy egy húszpontú gráf már akkor is tartalmaz
C4
-et, ha az
átlagfokszám legalább öt. Keressük meg, hogy melyik ponton akad el a
2.25. bizonyítása.
b) A
K.II.10.3. feladat felhasználásával válaszoljunk a következő kérdésre: Adott egy egyszerű (véges) gráf. Összeadjuk minden csúcsra a szomszédjaiból képezhető pontpárok számát. Hogyan becsülhető alulról ez az összeg az élszámmal (és a pontszámmal)?
Hogyan becsülhető ez az összeg felülről a pontszám segítségével, ha a gráfban nincs négypontú kör?
c) Bizonyítsuk be, hogy ha egy húszpontú egyszerű gráfnak legalább 50 éle van - azaz az átlagfokszáma legalább öt -, akkor van benne négypontú kör.
Feladat: 2.28. Bizonyítsuk be az előző,
2.27. feladatot a
2.26. feladat második megoldásában használt ,,cseresznyékkel".
Feladat: 2.29. *
a) Bizonyítsuk be, hogy ha egy
n pontú egyszerű gráfban nincs
C4
(négypontú kör), akkor legfeljebb
n(n+1)/2 éle van. Azaz
e4
(n)≤n(n+1)/2.
*** b) Mutassuk meg, hogy az a) feladat állítása nagyságrendileg pontos a következő értelemben. Végtelen sok
n-re van olyan
n2
-1 pontú, legalább
n2
(n-1)/2 élű egyszerű gráf, amelyben nincs négypontú kör. Vagyis végtelen sok
n-re igaz, hogy
e4
(n)≥n(n/2-1)/2.
Feladat: 2.30. Döntsük el a
2.29. feladat d) részének megoldása segítségével, hogy van-e olyan
m szám amelyre igaz a következő: ha egy gráfban minden pont foka legalább
m, akkor a gráf tartalmaz négypontú kört.