Bachelorprojekt for BSc-graden i...

D E T N A T U R V I D E N S K A B E L I G E F A K U L T E T K Ø B E N H A V N S U N I V E R S I T E T

Bachelorprojekt for BSc-graden i matematikMikkel Abrahamsen & Sune Precht Reeh

Ekstremal grafteori

Vejleder: Bergfinnur Durhuus

Afleveret: 25. juni 2008

Resume

Vi formulerer og beviser centrale resultater i ekstremal grafteori. Vi tager udgangspunkt i at un-dersøge mængden EX(n;F ) af ekstremale grafer for en given forbudt delgraf F og antallet ex(n;F )af kanter i disse ekstremale grafer. Projektet indeholder tre hovedresultater: Turans sætning, Erdos-Stones sætning og Szemeredis regularitetslemma. Turans sætning giver svar pa hvilke grafer derhar flest kanter uden at indeholde en given komplet graf Kr som delgraf. Erdos-Stones sætninggiver vigtig information om den asymptotiske opførsel af ex(n;F ) for en hvilken som helst forbudtdelgraf F eller mængde F af sadanne. Szemeredis regularitetslemma siger løst sagt at knudernei store grafer kan inddeles i klasser sa kanterne mellem to klasser er jævnt fordelt. Dette resultatbruges til at genbevise Erdos-Stones sætning, dog i en lidt svagere udgave. I afsnit 4 forsøger vi atvise mangfoldigheden af bevisteknikker i ekstremal grafteori ved at formulere tre mindre resultaterog give elementære beviser for disse.

Summary

We state and prove central results in extremal graph theory. We investigate the set EX(n;F ) ofextremal graphs without a given forbidden subgraph F and the number ex(n;F ) of edges in theseextremal graphs. Three main results of the project are: Turan’s Theorem, Erdos-Stone’s Theoremand Szemeredi’s Regularity Lemma. Turan’s Theorem tells us which graphs have the largest numberof edges without containing a given complete graph Kr as a subgraph. Erdos-Stone’s Theorem givesimportant information about the asymptotic behaviour of the function ex(n;F ) given a forbidddensubgraph F or a collection F of these. An informal formulation of Szemeredi’s Regularity Lemmais that the vertex set of large graphs can be partitioned such that the edges between two classesof vertices are evenly distributed. We give a proof of a slightly weaker version of Erdos-Stone’sTheorem using this regularity lemma. The purpose of section 4 is to formulate and give elementaryproofs of three minor results in extremal graph theory, and thereby give an impression of the varietyof techniques used in this field of mathematics.

2

Indhold

1 Indledning 4

2 Turans sætning 6

3 Erdos-Stones sætning 10

4 Et udvalg af interessante opgaver 184.1 Grafer med kredse af ulige længde . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184.2 Grafer med kredse af begrænset længde . . . . . . . . . . . . . . . . . . . . . . . . . 204.3 Grafer uden “butterflies” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5 Szemeredis regularitetslemma 26

6 Anvendelse af Szemeredis regularitetslemma 37

7 Notationsoversigt 41

3

1 Indledning

I dette projekt præsenterer vi et udvalg af resultater i ekstremal grafteori.I den bredeste forstand er ekstremal grafteori det omrade af grafteori der forsøger at bestemme

grafer der er “ekstremale” inden for forskellige familier af grafer. Typisk ser man pa familien afgrafer der har (eller ikke har) en given egenskab. Hvad der menes med “ekstremal” varierer ogsa fraproblem til problem: Man kan eksempelvis lede efter graferne med flest/færrest knuder, flest/færrestkanter, største/mindste minimale knudevalens.

I dette projekt vil de ekstremale grafer altid være graferne med flest kanter og et givent antalknuder. Som eksempler pa problemer af denne type kan vi nævne:

• Hvor mange kanter kan der være i en graf G med n knuder uden at G er sammenhængende?

• Hvor mange kanter kan der være i en graf G med n knuder uden at G indeholder en kreds?

• Hvor mange kanter kan der være i en graf G med n knuder uden at G indeholder Kr, enkomplet graf med r knuder?

• Hvor mange kanter kan der være i en graf G med n knuder uden at G indeholder to trekantermed netop en fælles knude?

De første to spørgsmal burde enhver studerende pa et indledende kursus i grafteori kunnesvare pa. En graf med n knuder som ikke er sammenhængende har flest kanter hvis den har tosammenhængskomponenter som hver især er komplette grafer, Kr og Kn−r. Derfor er svaret

maxr∈1,...,n−1

(r

2

)+(n− r

2

)=(n− 1

2

)=

(n− 1)(n− 2)2

.

Grafen har altsa flest kanter hvis den bestar af en isoleret knude og et eksemplar af Kn−1. Detandet problem har svaret at en graf har flest muligt kanter uden at indeholde en kreds hvis den eret træ, sa resultatet er n− 1.

Tredje og fjerde spørgsmal er derimod knapt sa enkle at svare pa. I afsnit 2 gives svar padet tredje spørgsmal, og det fjerde besvares i afsnit 4.3. Vi bemærker at man ækvivalent medeksempelvis det tredje spørgsmal kan spørge: “Hvor mange kanter skal der være i en graf G med nknuder sa vi med sikkerhed ved at Kr er en delgraf af G?”.

Et af de grundlæggende problemer i ekstremal grafteori er at bestemme de ekstremale grafergivet en forbudt delgraf eller en mængde af sadanne forbudte delgrafer. Med EX(n;F ) betegnesmængden af grafer med n knuder som har flest kanter uden at indeholde grafen F som delgraf (denforbudte graf), og graferne i EX(n;F ) kaldes ekstremale. Antallet af kanter i hver af de ekstrema-le grafer i EX(n;F ) betegnes ex(n;F ). Tilsvarende betegner EX(n;F) mængden af grafer med nknuder og flest muligt kanter som ikke indeholder nogen graf i en mængde F af forbudte delgrafer.I flere af resultaterne i projektet bestemmes sadanne ekstremale grafer. Andre gange gives der øvreeller nedre grænser for funktioner pa formen ex(n;F ) eller ex(n;F), eller den asymptotiske opførselaf disse funktioner bestemmes.

Projektet kan overordnet inddeles i tre dele: Afsnit 2 og 3 udgør første del. Her behandlesproblemet hvor den forbudte graf er den komplette graf Kr, og vi ser hvordan resultatet herfragiver den overordnede asymptotiske udvikling af ex(n;F) uanset familien F .

4

I projektets anden del, afsnit 4, ser vi pa tre konkrete opgaver. Vi haber herigennem at give etindtryk af hvor varieret ekstremal grafteori er i sine løsningsmetoder.

Tredje og sidste del er afsnit 5 og 6 hvor vi ser pa et af de stærke redskaber i ekstremal grafteori,Szemeredis regularitetslemma. Vi viser i praksis hvordan dette regularitetslemma kan anvendes vedat give at alternativt bevis for en af de store sætninger i projektets første del.

For at kunne læse projektet forudsættes et kendskab til indledende grafteori, f.eks. hvad mankan forventes at have tilegnet sig efter at have fulgt kurserne “Introduktion til diskret matematik ogalgebra” (Dis1&Alg1) og “Diskret matematik 2 og grafteori” (Dis2&Graf) pa Institut for Matema-tiske Fag, Københavns Universitet, hvilket er den primære baggrundsviden for begge forfatterne. Iafsnit 7 har vi givet en liste over den i projektet anvendte notation. Hvis læseren støder pa ukendtnotation henviser vi altsa til dette afsnit, der forhabentlig afklarer problemet.

Afsnittene 3 og 6 er hovedsageligt udfærdiget af Mikkel Abrahamsen, og afsnittene 2 og 5 afSune Precht Reeh.

5

2 Turans sætning

Den komplette graf Kr+1 er en af de mest simple og grundlæggende grafer med r+1 knuder, sa deter naturligt at spørge til hvilke grafer der er i mængden EX(n;Kr+1) af ekstremale grafer med nknuder. En r-partit1 graf indeholder ikke Kr+1, sa graferne i EX(n;Kr+1) har mindst lige sa mangekanter som de komplette r-partite grafer med n knuder der har flest kanter.

I dette afsnit viser vi at der er en entydigt bestemt r-partit graf med n knuder og flest kanter, ogat denne graf er den eneste graf i EX(n;Kr+1). Denne ekstremale graf betegnes Tr(n), og familienTr(n) | r, n ∈ N af disse grafer kaldes Turan-grafer efter Pal Turan (1910-1976). Resultatet kaldesligeledes Turans sætning.

Beviserne i dette afsnit bygger hovedsageligt pa beviserne i [BB] IV.2.Vi lægger ud med et resultat der er interessant i sig selv: For enhver graf G (r-partit eller ej)

der ikke indeholder Kr+1, findes en r-partit graf der knude for knude har mindst lige sa mangekanter som G.

Sætning 2.1 Lad G være en graf med knudemængde V der ikke indeholder Kr+1. Da findes enr-partit graf H med knudemængde V , sadan at for alle v ∈ V gælder

dG(v) ≤ dH(v).

Hvis G ikke er en komplet r-partit graf, findes en graf H der opfylder ovenstaende med skarp ulighedfor mindst en knude v ∈ V .

Bevis. Vi foretager induktion efter r. For r = 1 er K2 blot en enkelt kant, sa en graf G uden K2

er nødvendigvis den tomme graf med knudemængde V . Den tomme graf er den eneste komplette1-partite graf, sa pastanden gælder for r = 1.

Lad nu r > 1 og antag at pastanden gælder for lavere værdier af r. Lad x ∈ V være en knudemed maksimal valens, dG(x) = ∆(G). Delgrafen udspændt af naboknuderne til x, G0 = G[Γ(x)],indeholder ikke Kr, for en sadan Kr-delgraf vil sammen med x udgøre Kr+1.

Induktionsantagelsen giver nu at der findes en (r − 1)-partit graf H0 med knudemængde Γ(x),sa dH0(v) ≥ dG0(v) for alle v ∈ Γ(x). Desuden kan H0 vælges sa der er skarp ulighed for mindst etv ∈ Γ(x), med mindre G0 er en komplet (r−1)-partit graf. Vi udvider H0 til en r-partit graf H medalle knuderne i V , ved at lade V \ Γ(x) udgøre den sidste knudeklasse i H. Desuden lader vi alleknuder i V \ Γ(x) være forbundet til alle knuder i Γ(x). Vi pastar nu at H opfylder betingelserne isætningen.

Hvis v ∈ V \ Γ(x), er v forbundet i H til alle knuder i Γ(x) og inden andre, sa dermed er

dH(v) = |Γ(x)| = dG(x) ≥ dG(v).

Hvis derimod v ∈ Γ(x), er v forbundet til alle knuder i V \ Γ(x):

dH(v) = dH0(v) + |V \ Γ(x)| ≥ dG0(v) + |V \ Γ(x)| ≥ dG(v).

Hvad nu hvis dH(v) = dG(v) for alle v ∈ V ? Nar der gælder lighed ovenfor, ma der specieltgælde dH0(v) = dG0(v) for alle v ∈ Γ(x). Dermed ma G0 være en komplet (r − 1)-partit graf, oge(G0) = e(H0).

1Vi minder om at en graf er r-partit hvis knuderne kan deles i r klasser sa enhver kant gar fra en knude i en klassetil en knude i en anden klasse.

6

Figur 1: Turan-grafen T4(10).

Vi ser pa summen∑

v∈V \Γ(x) dG(v). Her er alle kanterne i G mellem Γ(x) og V \ Γ(x) blevettalt en gang, og alle kanterne mellem knuderne i V \ Γ(x) er blevet talt to gange:∑

v∈V \Γ(x)

dG(v) = eG(Γ(x), V \ Γ(x)) + 2e(G− Γ(x)) = e(G)− e(G0) + e(G− Γ(x)).

Da H er r-partit med V \ Γ(x) som en klasse, er e(H − Γ(x)) = 0. Ser vi pa∑

v∈V \Γ(x) dH(v), farvi saledes at ∑

v∈V \Γ(x)

dH(v) = e(H)− e(H0) + e(H − Γ(x)) = e(H)− e(H0).

Vi benytter nu at dH(v) = dG(v) for alle v ∈ V , sa e(H) = e(G).

e(G)− e(G0) = e(H)− e(H0) =∑

v∈V \Γ(x)

dH(v) =∑

v∈V \Γ(x)

dG(v) = e(G)− e(G0) + e(G− Γ(x)).

Vi har altsa at e(G − Γ(x)) = 0, sa der er ingen kanter i G mellem knuderne i V \ Γ(x). DadG(v) = dH(v) = |Γ(x)| for alle v ∈ V \ Γ(x), ma alle knuder i V \ Γ(x) være forbundet til alleknuder i Γ(x). Idet G0 er en komplet (r − 1)-partit graf, far vi endelig at G er en komplet r-partitgraf (med V \ Γ(x) som den sidste knudeklasse).

Definition 2.2 For r, n ∈ N er Turan-grafen, Tr(n), den komplette r-partite graf med n knudersadan at knuderne er fordelt sa ligeligt som muligt pa klasserne. Hvis n1 ≤ n2 ≤ · · · ≤ nr erantallene af knuder i klasserne i Tr(n), opfylder Tr(n) altsa nr ≤ n1 + 1. I figur 1 ses grafen T4(10)illustreret.

Antallet af kanter i Tr(n) betegnes tr(n).

Bemærkning 2.3 I Turan-grafen Tr(n) har n% r af klasserne størrelse⌈nr

⌉, og de resterende r−n% r

klasser har størrelse⌊nr

⌋(hvor n% r er den principale rest ved division af n med r).

Lemma 2.4 Tr(n) har flere kanter end alle andre r-partite grafer med n knuder.

Bevis. Lad G være en r-partit graf med n knuder. Hvis G ikke er en komplet r-partit graf, kanvi tilføje de resterende kanter mellem knudeklasserne i G, hvorved vi far en r-partit graf med flerekanter end G. De (kant)maksimale r-partite grafer ma saledes være komplette.

7

Antag derfor at G er en komplet r-partit graf forskellig fra Tr(n), og lad V1, V2, . . . , Vr væreknudeklasserne i G. Vi sætter ni = |Vi|, og antager uden tab af generalitet at n1 ≤ n2 ≤ · · · ≤ nr.

Lad x ∈ Vr, sa x er en knude fra den største klasse i G. Vi betragter nu den komplette r-partitegraf H med klasserne V1∪x, V2, V3, . . . , Vr−1, Vr \x. Vi har altsa fjernet alle kanterne mellem xog V1, og samtidig har vi tilføjet alle kanterne mellem x og Vr \x. Sammenligner vi kantantallenei G og H, far vi saledes at

e(H) = e(G)− n1 + (nr − 1) = e(G) + nr − (n1 + 1).

Da G ikke er Tr(n), gælder nr > n1 + 1, og dermed er e(H) > e(G). G er altsa ikke maksimal.Da grafer med n knuder højst har

(n2

)kanter, ma der være en maksimal r-partit graf. Denne

ma sa nødvendigvis være Tr(n).

Sætning 2.5 (Turans sætning) For r, n ∈ N, er ex(n;Kr+1) = tr(n), og EX(n;Kr+1) = Tr(n).

Bevis. Lad G = (V,E) være en graf der ikke indeholder Kr+1. Ifølge sætning 2.1 findes en r-partitgraf H sa dH(v) ≥ dG(v) for alle v ∈ V med lighed alle steder kun nar G er komplet r-partit.Specielt gælder at e(H) ≥ e(G) og der er kun lighed hvis G er en komplet r-partit graf.

Da H er r-partit giver lemma 2.4 at e(H) ≤ e(Tr(n)) = tr(n). Samlet set gælder altsa ate(G) ≤ tr(n), sa ex(n;Kr+1) ≤ tr(n). Omvendt er ex(n;Kr+1) ≥ tr(n) idet Turan-grafen Tr(n) err-partit og derfor ikke indeholder Kr+1.

Antag nu at e(G) = tr(n). Da gælder e(G) = e(H), sa G er komplet r-partit. G er altsa enr-partit graf med e(G) = e(Tr(n)). Lemma 2.4 giver dog at Tr(n) er den eneste maksimale r-partitegraf, sa vi ma nødvendigvis have G ' Tr(n).

Bemærkning 2.6 I den bipartite Turan-graf T2(n) har de to knudeklasser størrelse⌊n2

⌋og⌈n2

⌉.

Antallet af kanter i T2(n) er saledes

t2(n) =⌊n

2

⌋·⌈n

2

⌉=⌊n2

4

⌋,

hvilket lettest ses ved at dele op efter pariteten af n. Antallet af kanter i en trekantsfri graf med n

knuder er altsa (jf. Turans sætning) højst⌊n2

4

⌋.

Følgende resultat giver en generel øvre og nedre grænse for tr(n). Den øvre grænse kan f.eks.bruges til at konkludere eksistensen af Kr+1 i en given graf med n knuder og flere end (1 − 1

r )n2

2kanter, da Turans sætning giver at en graf med flere end tr(n) kanter ma indeholde Kr+1 somdelgraf.

Lemma 2.7 For alle n, r ∈ N gælder(1− 1

r

)(n

2

)≤ tr(n) ≤

(1− 1

r

)n2

2.

Bevis for nedre grænse. Lad r være fastholdt. Vi beviser grænsen ved induktion efter n. For n ≤ rer Tr(n) ' Kn, sa (

1− 1r

)(n

2

)<

(n

2

)= tr(n).

8

Vi vil nu vise pastandens rigtighed for n + 1 > r, og antager at den er rigtig for n. Det sesat tr(n + 1) = tr(n) + n −

⌊nr

⌋, idet Tr(n + 1) fremkommer ved at tilføje en knude til en mindste

knudeklasse i Tr(n) og forbinde den med alle knuder i de øvrige klasser. Dermed har vi

tr(n+ 1) = tr(n) + n−⌊nr

⌋≥(

1− 1r

)(n

2

)+ n− n

r=(

1− 1r

)(n+ 1

2

).

Bevis for øvre grænse. Ved n% r forstas den principale rest af n ved division med r. Det viser sigat være mere praktisk at betragte den komplementære graf Tr(n), sa vi vil vise

e(Tr(n)) =(n

2

)− tr(n) ≥

(n

2

)−(

1− 1r

)n2

2=n2

2r− n

2.

Tr(n) er foreningen af n% r eksemplarer af Kdnr e og r−n% r eksemplarer af Kbn

r c. Antag førstat r | n. Sa har vi

e(Tr(n)) = r

(nr

2

)=n2

2r− n

2,

som skulle vises.Hvis r - n, er

⌈nr

⌉= 1

r (n+ r − n% r) og⌊nr

⌋= 1

r (n− n% r). Vi har sa

e(Tr(n)) = (n% r)(⌈n

r

⌉2

)+ (r − n% r)

(⌊nr

⌋2

)= (n% r)

⌈nr

⌉2

2+ (r − n% r)

⌊nr

⌋2

2− (n% r)

⌈nr

⌉2− (r − n% r)

⌊nr

⌋2

=1

2r2

[(n% r)(n2 + 2n(r − n% r) + (r − n% r)2) + (r − n% r)(n2 − 2n(n% r) + (n% r)2)

]− 1

2r[(n% r)(n+ r − n% r) + (r − n% r)(n− n% r)]

=(n% r)(r − n% r) · r

2r2+n2

2r− n

2

≥ n2

2r− n

2.

9

3 Erdos-Stones sætning

Lad r ∈ N og ε > 0 være vilkarlige og i det følgende faste tal. Turan-grafen Tr(n) indeholder ikkeen komplet delgraf med r + 1 knuder, Kr+1, og ifølge lemma 2.7 er tr(n) ≥ (1 − 1

r )(n2

). En graf

med (1 − 1r )(n2

)kanter behøver altsa ikke indeholde Kr+1 som delgraf. I dette afsnit viser vi dog

at for et givet t ∈ N vil en graf med blot ε(n2

)kanter flere, altsa (1 − 1

r + ε)(n2

)kanter, indeholde

Kr+1(t) (den komplette (r + 1)-partite graf med t knuder i hver klasse), hvis bare n er stor nok.Dette resultat kaldes Erdos-Stones sætning efter Paul Erdos (1913-1996) og Arthur Harold Stone(1916-2000) og er fra 1946.

Lad n(t) være det mindste tal sa Kr+1(t) er indeholdt i enhver graf med n(t) knuder og(1 − 1

r + ε)(n(t)

2

)kanter. Vi viser at n(t) = O(exp t), men vi viser ikke at denne grænse er den

bedst mulige. I [BB] s. 122 bemærkes det dog at det vha. Szemeredis regularitetslemma er muligtat vise at n(t) = Ω(exp t).

Som korollar til Erdos-Stones sætning viser vi at grænseværdien

limn→∞

ex(n;F)(n2

)eksisterer for en hvilket som helst mængde af grafer F . Vi viser endda at grænseværdien er givetved 1− 1

r , hvor r er det mindste tal sa der findes en graf F ∈ F og et tal t ∈ N sa F er en delgrafaf Kr+1(t). Dette tal r er altid defineret da en graf F med n knuder er indeholdt i Kn = Kn(1).Specielt kan vi udregne

limn→∞

ex(n;G)(n2

)for enhver graf G, hvis bare vi kender det mindste r sa G er en delgraf i Kr+1(t) for et t ∈ N.

Vi kan altsa bestemme den asymptotiske tæthed af de ekstremale grafer for en hvilken som helstsamling af forbudte delgrafer, dvs. forholdet mellem kantantallet i en ekstremal graf med n knuderog kantantallet i den komplette graf med n knuder. Vi kan kun bestemme koefficienten til n2-leddeti den asymptotiske opførsel af ex(n;F) – hvordan funktionen ex(n;F) i øvrigt opfører sig kan viikke sige. Vi kan heller ikke sige noget om hvordan strukturen af graferne i EX(n;F) er, men denovenfor nævnte tæthed ma alligevel siges at være vigtig information om de ekstremale grafer.

I dette afsnit bygger resultaterne og beviserne hovedsageligt pa fremstillingen givet i [BB] afsnitIV.4.

Bemærkning 3.1 Funktionen f(x) = x log x har den afledte funktion f ′(x) = 1 + log x. Funktionenf er altsa aftagende for 0 < x ≤ e−1 og voksende for x ≥ e−1. Specielt antager f(x) minimum ie−1, og vi far saledes

x log x ≥ −1e> −1

2> −2

3.

Dette lille resultat far vi brug for to gange i de følgende beviser.

Definition 3.2 I en graf G siges en knude v at dække en delgraf H ⊆ G safremt v er forbundet tilalle knuder i H.

Lemma 3.3 For ethvert fast 0 < ε < 1 vil en graf G med n knuder og δ(G) ≥ εn indeholde K2(t)som delgraf for t = dε log ne, hvis bare n er stor nok.

10

Bevis. Antag at G = (V,E) er en graf med n knuder og δ(G) ≥ εn, som ikke indeholder K2(t) fort = dε log ne. Lad A være antallet af par pa formen (v, T ), hvor v ∈ V og T er en delmængde af Vmed t knuder, som er dækket af v. Vi har nu n

(dεnet

)≤ A, idet hver af de n knuder mindst dækker(dεne

t

)mængder af t knuder, da δ(G) ≥ dεne. Vi har ogsa A < t

(nt

), da hver delmængde af V pa t

knuder er dækket af færre end t knuder, idet G ellers ville indeholde K2(t). Dermed er

n

(dεnet

)< t

(n

t

).

Nu vil vi vise at denne ulighed ikke er opfyldt, hvis n er tilstrækkeligt stor. Vi har:

t(nt

)n(dεne

t

) ≤ t

n

nt

(dεne − t)t≤ t

n

nt

(εn− t)t=t

n

(1

ε− tn

)t=t

nε−t(

1− t

εn

)−t=t

nε−dε logne

(1− dε log ne

εn

)−dε logne≤ t

nε−ε logn−1

(1− ε log n+ 1

εn

)−ε logn−1

≤ t

nε−ε logn−1

(1− 2 log n

n

)−ε logn−1

,

hvor sidste ulighed gælder nar n er stor nok, idet vi sa har ε log n+ 1 ≤ 2ε log n.

Det ses at(

1− 2 lognn

)−ε logn→ 1 for n→∞ idet logartimen af udtrykket opfylder

−ε log n log(

1− 2 log nn

)= 2ε · (log n)2

n·

log(1− 2 lognn )

−2 lognn

→ 2ε · 0 · 1 = 0

for n→∞.Vi har ogsa, ved at bruge bemærkning 3.1

t

nε−ε logn−1 =

t

εnn−ε log ε ≤ t

εnn2/3 =

dε log neεn1/3

→ 0

for n→∞.Det giver nu

t

nε−ε logn−1

(1− 2 log n

n

)−ε logn−1

=t

nε−ε logn−1

(1− 2 log n

n

)−ε logn(1− 2 log n

n

)−1

→ 0 · 1 · 1 = 0

for n→∞. Dette viser at t(nt

)/n(dεne

t

)→ 0 for n→∞, sa t

(nt

)≤ n

(dεnet

)nar n er stor nok. Dermed

vil enhver graf G med n knuder og δ(G) ≥ εn indeholde K2(t) hvis n er stor nok.2

2I [BB] s. 120 foretages vurderingen

t(

nt

)n(

εnt

) ≤ · · · ≤ 2t

εnn1/ε < 1,

hvor det sidste ulighedstegn er forkert, da vi faktisk har 2tεnn1/ε →∞ for n→∞.

11

Sætning 3.4 Lad r ∈ N og 0 < ε < 1r . Da findes et N = N(r, ε), sadan at hvis G har n ≥ N

knuder og

δ(G) ≥(

1− 1r

+ ε

)n,

sa er Kr+1(t) en delgraf af G hvor

t =⌈

ε log n2r(r − 1)!

⌉.

Bevis. Vi anvender induktion efter r. Basistilfældet r = 1 følger af lemma 3.3, sa vi fortsætterdirekte til induktionsskridtet.

Antag derfor at r ≥ 2 og at G er en graf med n knuder og

δ(G) ≥(

1− 1r

+ ε

)n >

(1− 1

r

)n =

(1− 1

r − 1+

1r(r − 1)

)n.

Induktionsantagelsen giver os da at for n ≥ N(r−1, 1r(r−1)) indeholder G en delgraf K = Kr(T )

hvor

T =

⌈1

r(r−1) log n

2r−1(r − 2)!

⌉=⌈

21−r

r!log n

⌉. (3.1)

Lad U være mængden af de knuder i G−K der har mindst (1− 1r + ε

2) |K| kanter til knuder iK. Vi pastar nu at |U | ≥ εn for n tilstrækkelig stor.

Bevis for pastanden. Vi ser pa antallet A af kanter mellem K og G−K. Ifølge antagelsen i sætning3.4 har enhver knude i K valens mindst (1− 1

r + ε)n. En knude i K er derfor forbundet til mindst(1− 1

r + ε)n− |K| knuder uden for K. Nar vi summerer over knuderne i |K| far vi dermed

A ≥ |K|((

1− 1r

+ ε

)n− |K|

)Samtidig er de knuder i G−K der ikke ligger i U , højst forbundet til (1− 1

r + ε2) |K| knuder i K.

Knuderne i U er naturligvis højst forbundet til |K| knuder i K. Samlet set far vi altsa

A ≤ |U | |K|+ (n− |K| − |U |)(1− 1r + ε

2) |K| ≤ |U | |K|+ (n− |U |)(1− 1r + ε

2) |K| .

Nu sammensætter vi de to uligheder og dividerer igennem med |K|; dette giver os(1− 1

r+ ε

)n− |K| ≤ |U |+ (n− |U |)(1− 1

r + ε2).

Lægges |K| − (1− 1r + ε

2)n til pa begge sider, fas efterfølgende

ε2n ≤ |U | (

1r −

ε2) + |K| . (3.2)

12

Antag nu for modstrid at |U | < εn. Vi kan da opvurdere højresiden ovenfor:

|U | (1r −

ε2) + |K| < εn(1

r −ε2) + |K|

= εrn−

ε2

2 n+ |K|

≤ ε2n−

ε2

2 n+ |K| .

Størrelsen |K| = r · T = r⌈21−r 1

r! log n⌉

vokser, som funktion af n, asymptotisk som r21−r 1r! log n.

Vi ser dermed at ε2

2 n ≥ |K| nar n er stor nok. Lad N ′ ∈ N (hvor N ′ ≥ N(r− 1, 1r(r−1))) opfylde at

ε2

2 n ≥ |K| for n ≥ N ′.

Nar n ≥ N ′, far vi dermed |U | (1r −

ε2) + |K| < ε

2n i modstrid med (3.2). For n ≥ N ′ gælder altsaat |U | ≥ εn.

Sæt nu

t =⌈


⌉=⌈εr

2· 21−r

r!log n

⌉.

Fra ligning (3.1) ses dermed t ≤⌈εr2 T⌉, saledes at⌈

(1− 1r + ε

2) |K|⌉

=⌈(1− 1

r + ε2)r · T

⌉= (r − 1)T +

⌈εr2 T⌉≥ (r − 1)T + t.

Dette viser at enhver knude i U er forbundet til mindst t knuder i hver klasse i K, det vil altsa sigeat enhver knude i U dækker en Kr(t)-delgraf af K.

I K findes(Tt

)reksemplarer af delgrafen Kr(t) (disse er karakteriseret ved valg af t knuder i

hver af de r klasser i K). Der er gennemsnitligt mindst |U | /(Tt

)rknuder i U der dækker hver Kr(t)-

delgraf. Dermed findes specielt en delmængde W ⊆ U af knuder der dækker samme Kr(t)-delgraf,og sadan at

|W | ≥ |U | /(T

t

)r.

Vi ønsker nu at vise |W | ≥ t. Til dette skal vi dog bruge nogle forberedelser. Lad N ′′ ∈ N sadanat

1 + 2r−1 1r! log n

2r−1 1r! log n

≤ 3e

for n ≥ N ′′. For alle n ≥ N ′′ gælder da

t

eT=⌈


⌉· 1e·⌈21−r 1

r! log n⌉−1

≥ ε log n2r(r − 1)!

· 1e· (1 + 21−r 1

r! log n)−1

≥ ε log n2r(r − 1)!

· 13· (21−r 1

r! log n)−1 =εr

6

≥ ε

3.

Derudover giver en klassisk ulighed relateret til Stirlings formel (jf. [MN] s. 77)

t! ≥ e(t

e

)t≥(t

e

)t.

13

Med disse iagttagelser fortsætter vi nu med at vurdere størrelsen af W :

|W | ≥ |U | /(T

t

)r≥ |U | ·

(t!T t

)r≥ |U | ·

(t

eT

)tr≥ εn

(t

eT

)tr≥ εn

(ε3

)tr= εn exp

(tr log

(ε3

)).

I dette udtryk ser vi at log( ε3) er negativt idet ε < 3. Hvis tr vurderes op, vil det samlede negativeprodukt tr log( ε3) blive vurderet nedad. Da exp er en voksende funktion, fas saledes:

|W | ≥ εn exp(tr log

(ε3

))≥ εn exp

((ε log n

2r(r − 1)!+ 1)· r · log

(ε3

))= εn exp

(ε log n

2r(r − 1)!r log

(ε3

)+ r log

(ε3

))= ε

(ε3

)rn exp

(ε

2log(ε

3

) r

2r−1(r − 1)!log n

)> ε

(ε3

)rn · nα.

Her har vi sat α = ε2 log

(ε3

)r

2r−1(r−1)!.

Idet r ≥ 2, er r ≤ 2(r − 1). Dermed gælder i endnu højere grad

r ≤ 2r−1(r − 1)!.

Fra bemærkning 3.1 følger at ε2 log

(ε3

)> −1.3 Sammenholdes dette med ovenstaende fas

α =ε

2log(ε

3

) r

2r−1(r − 1)!> −1 · 1 = −1.

Saledes er |W | ≥ ε(ε3

)rn1+α, hvor α > −1. Da vi dermed har 1+α > 0, og da t vokser asymptotisk

som log n, findes N ′′′ ∈ N sadan at

ε(ε

3

)rn1+α ≥ t for n ≥ N ′′′.

Sæt nu N(r, ε) = max(N ′, N ′′, N ′′′), da gælder for n ≥ N(r, ε) at |W | ≥ t. Ved eventuelt at fjerneknuder fra W , kan vi opna at |W | = t.

Da alle knuderne i W dækker den samme Kr(t)-delgraf i K, danner denne delgraf sammen medW en Kr+1(t) delgraf af G med t =

⌈ε logn

2r(r−1)!

⌉.

Lemma 3.5 Lad c, ε > 0. Enhver graf med n > 3ε knuder og mindst (c+ ε)

(n2

)kanter indeholder en

delgraf H med mindst√εn knuder for hvilken δ(H) ≥ c|H|.

3I [BB] foretages den forkerte vurdering ε log(ε/3) > −1. Til forskel fra de mange andre smafejl i beviset i [BB],har denne fejl betydning for sætningens formulering: Vores værdi af t i Erdos-Stones sætning er halvt sa stor somden i [BB] anførte værdi pa grund af denne fejl.

14

Bevis. Lad G være en graf med n > 3ε knuder med mindst (c + ε)

(n2

)kanter. Bemærk at 0 < ε <

c+ε ≤ 1, da det maksimale antal kanter er(n2

). Antag for modstrid at G ikke indeholder en delgraf

af den beskrevne beskaffenhed. Lad Gn = G og lad rekursivt Gj−1 være en graf fremkommet ved atfjerne en knude vj af minimal valens fra Gj . Sæt k = b

√εnc. For n ≥ j > k ma vi have dGj (vj) < cj,

for ellers ville Gj være en delgraf af den ønskede type. Saledes er

e(Gk) = e(G)−n∑

j=k+1

dGj (vj) > (c+ ε)(n

2

)−

n∑j=k+1

cj

= (c+ ε)(n

2

)− c

((n+ 1

2

)−(k + 1

2

))= ε

(n

2

)+ c

((k + 1

2

)− n

)> ε

(n

2

)+ c

(√εn(√εn− 1)2

− n)> ε

(n

2

)+ c

(3n−

√εn

2− n

)= ε

(n

2

)+ c

n(1−√ε)

2> ε

(n

2

)=√εn(√εn−

√ε)

2>b√εnc (b

√εnc − 1)

2

=(k

2

).

Det er en modstrid, da Gk højst kan have(k2

)kanter.

Sætning 3.6 (Erdos-Stones sætning) Lad r ∈ N og 0 < ε < 1r . Sa findes et heltal N = N(r, ε) sa

enhver graf G med n ≥ N knuder og

e(G) ≥ (1− 1r

+ ε)(n

2

)kanter indeholder Kr+1(t) for et t ∈ N der opfylder

t >ε log n

2r+2(r − 1)!.

Bevis. Hvis n > 3ε/2 indeholder G ifølge lemma 3.5 en delgraf H med h ≥

√ε2n knuder og hvor

δ(H) ≥ (1 − 1r + ε

2)h, idet G har mindst (1 − 1r + ε

2 + ε2)(n2

)kanter.4 Hvis n er stor nok har vi sa

ifølge sætning 3.4 at H, og dermed G, indeholder Kr+1(t), hvor

t =⌈ ε

2 log h2r(r − 1)!

⌉≥ε log

(√ε2n)

2r+1(r − 1)!.

Da

log(√

ε

2n

)=

12

logε

2+ log n >

12

logε

6+ log n = −1

2log

3ε/2

+ log n ≥ 12

log n,

har vi

t >ε log n

2r+2(r − 1)!,

som ønsket.4I [BB] star fejlagtigt at vi kan finde en sadan delgraf H med h ≥

√εn knuder. Det garanterer lemma 3.5 ikke.

15

Korollar 3.7

ex(n;Kr+1(t)) =(

1− 1r

)(n

2

)+ o(n2).

Bevis. Vi ved, at Tr(n) ikke indeholder Kr+1(t) for noget n, sa ex(n;Kr+1(t)) ≥ e(Tr(n)) ≥(1− 1

r

) (n2

)ifølge lemma 2.7. Antag at pastanden ikke holder for et givet t ∈ N. Da findes der

ε > 0 sa der findes vilkarligt store n som opfylder

ex(n;Kr+1(t)) ≥(

1− 1r

)(n

2

)+ εn2 >

(1− 1

r+ 2ε

)(n

2

).

Sa giver Erdos-Stones sætning at graferne i EX(n;Kr+1(t)) for n stor nok indeholder Kr+1(t).Det er en modstrid.

Korollar 3.8 Lad F være en mængde af ikke-tomme grafer. Lad r + 1 være det mindste tal sadanat der findes en graf i F der er indeholdt i Kr+1(t) for et t ∈ N. Sa er

ex(n;F) =(

1− 1r

)(n

2

)+ o(n2).

Dermed erlimn→∞

ex(n;F)(n2

) = 1− 1r.

Bevis. Da Kr(t) ikke indeholder en graf fra F for noget t ∈ N kan heller ikke Turan-grafen Tr(n)indeholde en graf fra F for noget n ∈ N, sa vi har fra lemma 2.7

ex(n;F) ≥ e(Tr(n)) ≥(

1− 1r

)(n

2

).

Antag nu at F ∈ F er en delgraf af Kr+1(t). Hvis en graf ikke indeholder F indeholder dendermed heller ikke Kr+1(t), sa vi har ifølge korollar 3.7

ex(n;F) ≤ ex(n;F ) ≤ ex(n;Kr+1(t)) =(

1− 1r

)(n

2

)+ o(n2).

Bemærkning 3.9 I korollaret ovenfor kan det være nemmere at tænke pa r + 1 som det mindsteaf de (knude)kromatiske tal χ(F ) for F ∈ F . En graf har nemlig kromatisk tal r + 1 hvis og kunhvis den (r + 1)-partit, og den er (r + 1)-partit hvis og kun hvis den er indeholdt i Kr+1(t) for etstort nok t.

Bemærkning 3.10 Den i korollar 3.8 angivne grænseværdi er ikke nødvendigvis nem i praksis atbestemme, idet vi skal bestemme det mindste at de kromatiske tal χ(F ) for F ∈ F . At bestemmedet kromatiske tal for en graf er nemlig et NP-hardt problem, jf. [KC]. Vi vil ikke her kommenærmere ind pa det tekniske indhold af dette, men kun bemærke at det betyder at man med alrimelighed ma forvente at den tid det tager at bestemme χ(G) for en graf G med n knuder vokser(som funktion af n) hurtigere end ethvert polynomium.

16

Vi giver nu en anvendelse af Erdos-Stones sætning indenfor et tilsyneladende fjernt matematiskomrade. Resultatet stammer fra [PE], men er ogsa stillet som opgave 42.+ i [BB]:

Korollar 3.11 Lad Gk(n), k ≥ 2, være det maksimale antal gange samme afstand kan forekommemellem n punkter i Rk (malt med den sædvanlige metrik). Da gælder

Gk(n)n2

→ 12− 1

2⌊k2

⌋ for n→∞. (3.3)

Bevis. Lad l =⌊k2

⌋.

Først vises at hvis G′k(n) = Gk(n)n2 konvergerer, sa er grænseværdien mindst det pastaede. For

ethvert t = 1, . . . , l lader vi Pt være en mængde af⌊nl

⌋punkter i R2l sa

Pt ⊂ (x1, . . . , x2l) ∈ R2l | xi = 0, i 6∈ 2t− 1, 2t, x22t−1 + x2

2t =12.

Sa er afstanden mellem et punkt i Pi og et punkt i Pj for i 6= j klart√

12 + 1

2 = 1. Dvs. at dermindst er (

l

2

)⌊nl

⌋2≥ l(l − 1)

2

(nl− 1)2

=n2

2− nl +

l2

2− n2

2l+ n− l

2

ens afstande.Vi ma klart have Gk(n) ≥ Gk−1(n), da n punkter i Rk−1 med en afstand forekommende g gange

kan indlejres i Rk sa samme afstand forekommer g gange. Da k ≥ 2⌊k2

⌋= 2l har vi derfor

G′k(n) ≥ G′2l(n) ≥n2

2 − nl + l2

2 −n2

2l + n− l2

n2=

12− 1

2l+−ln+ l2

2 + n− l2

n2→ 1

2− 1

2l=

12− 1

2⌊k2

⌋for n→∞.

Vi bruger Erdos-Stones sætning til at vise at G′k(n) nødvendigvis ma konvergere mod detpastaede. Hvis ikke fandtes der nemlig et ε > 0 sa vi for vilkarligt store n havdeG′k(n) ≥ 1

2−1

2b k2c

+ε.

Dermed ville

Gk(n) ≥(

12− 1

2l+ ε

)n2 =

(1− 1

l+ 2ε

)n2

2>

(1− 1

l+ 2ε

)(n

2

),

for vilkarligt store n. Vi kan for ethvert n betragte en mængde Mn af n punkter i Rk sa flest muligtafstande mellem punkterne i Mn er ens – lad dn være en afstand der forekommer flest gange. Viser pa grafen Gn = (Mn, En) hvor x, y ∈ En hvis ||x− y|| = dn. Ovenstaende giver ifølge Erdos-Stones sætning at vi for et N ≥ N(l, 2ε) har at GN indeholder Kl+1(3). Dvs. at en delmængde Maf punkterne i MN kan deles op i l + 1 klasser af tre punkter x(t)

i , i = 1, 2, 3, t = 1, . . . , l + 1, saafstanden mellem x

(t1)i1

og x(t2)i2

er lig med dn for alle punkter x(t1)i1

og x(t2)i2

, t1 6= t2.Et geometrisk argument (som vi her kun skitserer) viser, at dette ikke kan lade sig gøre. Punk-

terne x(t)1 , x

(t)2 , x

(t)3 kan ikke ligge pa linje, da alle øvrige punkter i M skal have samme afstand til

dem alle tre. Dermed ma de udspænde en plan P = P (x(t)1 , x

(t)2 , x

(t)3 ), og alle øvrige punkter proji-

ceret pa P ma være centrum for den entydigt bestemte cirkel indeholdende x(t)1 , x

(t)2 , x

(t)3 . De øvrige

l klasser af punkter er altsa indeholdt i en (k − 2)-dimensional delmængde af Rk. Det ses saledesat dimensionen af rummet udspændt af de l+ 1 klasser af punkter mindst er 2(l+ 1) = 2l+ 2 > k,hvilket er en modstrid.

17

4 Et udvalg af interessante opgaver

I dette afsnit løser vi tre opgaver i ekstremal grafteori. Alle opgaverne gar ud pa at bestemme deekstremale grafer der ikke har en delgraf af en nærmere specificeret type. Løsningerne benytter sigkun af elementære observationer – der bruges (næsten) ikke nogen i forvejen kendte resultater. Vihar taget opgaverne med for at vise andre sider af den ekstremale grafteori, og har derfor valgtat placere afsnittet omtrent i midten som et lille intermezzo. De strategier der anvendes til atbestemme ekstremale grafer i de tre opgaver er helt forskellige og giver derved en fornemmelse afat man ikke uden videre kan give en mekanisk opskrift pa hvordan ekstremale grafer bestemmesgenerelt.

4.1 Grafer med kredse af ulige længde

Som bekendt er en graf bipartit hvis og kun hvis alle dens kredse har lige længde. Ifølge 2.4 harT2(n) flest kanter blandt de bipartite graf med n knuder, sa vi har altsa EX(n;U) = T2(n), hvorU er mængden af kredse af ulige længde.

Vi vil nu bestemme EX(n;L), hvor L er mængden af kredse af lige længde. Fra korollar 3.8 vedvi i forvejen at ex(n;L) = o(n2), da f.eks. en kreds af længde 4 er indeholdt i K2(2). Vi far brugfor følgende definition:

Definition 4.1 En delgraf B af en graf G kaldes en blok af G hvis B er to kantforbundne knuderv, w, sadan at vw er en bro i G (altsa sa G− vw har flere sammenhængskomponenter end G) ellerhvis B er en maksimal 2-sammenhængende5 delgraf i G. Bemærk at enhver kant i G er indeholdt ien entydigt bestemt blok.

De følgende resultater har vi selv formuleret og bevist. Først et lille lemma generelt om graferder kun har kredse af ulige længde.

Lemma 4.2 I en graf hvor alle kredse har ulige længde, har to kredse højst en fælles knude.

Bevis. Lad G være en graf hvori alle kredse har ulige længde. Antag for modstrid at kredseneK1 = v1 · · · vp og K2 = w1 · · ·wq i G har mere end en knude til fælles. Vi kan uden tab af generalitetantage at v1 = w1 samt at v2 /∈ K2 (idet K1 ikke kan være helt indeholdt i K2).

Vi lader i = minr ≥ 3 | vr ∈ K2 og lader j opfylde vi = wj . Tallene i−1 og j−1 har forskelligparitet idet kredsen v1v2 · · · viwj−1wj−2 · · ·w2 ellers vil have lige længde. Tallene q − j + 1 og i− 1skal ogsa have forskellig paritet, idet kredsen v1v2 · · · viwj+1wj+2 · · ·wq ellers har lige længde. Mendet giver at j − 1 + q− j + 1 = q er lige, som er en modstrid. Her har vi to gange brugt antagelsenom at vl /∈ K2 for l = 2, . . . , i− 1 til at slutte at ingen knude i de nævnte lister gentages, sadan atder vitterligt er tale om kredse.

Sætning 4.3 EX(n;L) for n ≥ 2 er de sammenhængende grafer med n knuder, højst en bro og hvisøvrige blokke alle er trekanter. Dermed er

ex(n;L) =

3n−42 , n lige

3n−32 , n ulige.

I figur 2 ses et eksempel pa en ekstremal graf.5Vi minder om at en graf G er 2-sammenhængende hvis G− v er sammenhængende for enhver knude v ∈ V (G).

18

Figur 2: En ekstremal graf med 14 knuder uden kredse af lige længde.

Bevis. Lad G være en af de pastaede ekstremale grafer med n knuder. Hvis n = 2m er lige ses vedinduktion efter antallet af blokke at G indeholder en bro samt m − 1 = n−2

2 trekantsblokke (derbruges to knuder til broen og to knuder til hver yderligere blok – der er trekantsblokke). I sa faldindeholder grafen 3n−2

2 + 1 = 3n−42 kanter. Hvis n = 2m+ 1 er ulige, ses tilsvarende at G bestar af

m trekantsblokke, sa G har 3m = 3n−32 kanter.

Pastanden ses at gælde for n = 2, sa antag n ≥ 3 og at pastanden gælder for mindre n. Vibemærker først at ex(n;L) ≥ n: En vejgraf med n knuder hvor første og tredje knude desuden erkantforbundne, har nemlig n kanter og kun en enkelt (ulige) kreds. Lad G ∈ EX(n;L), G = (V,E).Grafen G ma da være sammenhængende med mindst n kanter. G har dermed en kreds. Vi serendvidere at G højst har en bro: Antag nemlig at kanterne ab og cd begge er broer. Vi kan nusammentrække knuderne a og b og knuderne c og d og derved fa en graf G0 med n − 2 knuder oge(G)− 2 kanter, som heller ikke indeholder kredse af lige længde. Ved at tilføje to knuder e og f ogdanne trekanten vef med en knude v ∈ V (G0), fas en graf med n knuder og e(G) + 1 kanter. Detteer en modstrid, da G var antaget at være ekstremal.

Betragt en kreds K = v1 · · · vk i G. Lad G1 = G−E(K) være grafen hvor vi har fjernet kanternei K fra G. To knuder vi, vj ∈ V (K), i < j, kan ikke være i samme sammenhængskomponent i G1, davi i sa fald har en vej vj

π−→ vi kantdisjunkt med K. Derfor vil vi i G have en kreds vivi+1 · · · vjπ−→ vi

som har to knuder til fælles med K. Ifølge lemma 4.2 medfører dette at G indeholder en kreds aflige længde. Til hver knude vi ∈ V (K) svarer altsa en entydigt bestemt sammenhængskomponentVi indeholdende vi i G1. Vi har færre end n knuder og er nødvendigvis ekstremal (ellers ville G ikkevære ektremal), sa induktionsantagelsen giver at blokkene i Vi er trekantsblokke og højst en bro.Desuden kan højst en af komponenterne V1, . . . , Vk indeholder en bro. Ved at vise at k = 3 har vidermed vist det ønskede, for blokkene i G er netop K og blokkene i V1, . . . , Vk.

Vi transformerer G til en graf G′ = (V,E′) meget lignende G, men hvor vi har flyttet vissekanter. E′ er E hvor vi har fjernet alle kanter gaende fra vi til knuder uden for K for i = 2, . . . , k,og de knuder uden for K der herved mister en kant forbindes i stedet til v1. Mere formelt:

E′ =

(E \

k⋃i=2

viw ∈ E | w /∈ K

)∪

k⋃i=2

v1w | w /∈ K, viw ∈ E.

Vi bemærker at de kanter der tilføjes, ikke ligger i E i forvejen, for ellers ville G indeholde tokredse med to knuder til fælles. Det ses heraf at G′ har lige sa mange kanter som G. Nu viser vi atG′ ikke kan indeholde nogen kredse af lige længde: Hvis G′ indeholder en kreds L af lige længde,ma der i denne kreds indga en kant pa formen v1w, w 6∈ K, der stammer fra en kant viw ∈ E, i ≥ 2,(fordi L ma indeholde en af kanterne i E′ \ E). L kan ikke indeholde andre knuder fra K, da deneneste knude i K der er forbundet til knuder uden for K i G′, er v1. Dermed ma L indeholde endnu

19

en kant pa formen v1u hvor u /∈ K, sa G indeholder en kant for formen vju for j ≥ 1. Der ma findesen vej wx1 · · ·xpu fra w til u i L, der ikke indeholder knuder fra K, sa vi har L = v1wx1 · · ·xpu.Vi kan ikke have i = j, da G i sa fald ville indeholde en kredsen viwx1 · · ·xpu af lige længde. Mendermed indeholder G jo vejen viwx1 · · ·xpuvj fra vi til vj , som er kantdisjunkt med K. Denne vejkan udvides (med knuder fra K) til en kreds der har bade vi og vj til fælles med K. Ifølge lemma4.2 medfører dette at G indeholder en kreds af lige længde. Altsa indeholder G′ ingen kreds af ligelængde.

Vi sætter H = G′ − v2, . . . , vk, sa K og H indeholder tilsammen alle knuder og kanter i G′.Vi ma have H ∈ EX(n− k + 1;L), da G′, og dermed G, ellers ikke havde været ekstremal. Antagførst at n, og dermed n − k + 1, er lige. Induktionsantagelsen giver os at H indeholder en bro, ogat de øvrige blokke i H er trekanter, samt at

e(G) = e(G′) = e(H) + e(K) =3(n− k + 1)− 4

2+ k =

3n− 12− k

2.

Det ses at e(G) er størst hvis k er sa lille som muligt, dvs. hvis k = 3. Dermed har G den ønskedeform. Tilfældet hvor n er ulige behandles tilsvarende.

Vi har nu vist at alle ekstremale grafer er pa den pastaede form, men det ma medføre at allegrafer pa den form er ekstremale, idet de indeholder lige mange kanter og ikke indeholder kredse aflige længde.

4.2 Grafer med kredse af begrænset længde

I dette afsnit ser vi for et k ∈ N pa grafer der ikke indeholder kredse af længde større end k.Sætning 4.5 (med beviset stillet som opgave 39.+ i [BB]) nedenfor siger at en sadan graf G opfyldere(G) ≤ k

2 (n − 1). Vi finder ogsa de ekstremale grafer (de grafer hvor der gælder lighedstegn iuligheden), men som vi skal se kan der kun gælde lighedstegn for n ≡ 1 (mod k − 1). Det er altsakun for nogle n ∈ N at vi bestemmer EX(n;F) – hvor F = Ci | i > k er mængden af kredse aflængde større end k. For andre værdier af n har vi ikke fundet ud af at beskrive graferne i EX(n;F)eller bestemme antallet ex(n;F) af kanter i disse grafer. Dette er en markant afvigelse fra Turanssætning, sætning 4.3 og sætning 4.6 hvor vi er i stand til eksplicit at finde de ekstremale grafer foralle antal n af knuder.

Definition 4.4 Lad a = v1 · · · vr være en vej af maksimal længde i grafen G. Da vejen ikke kanudvides er Γ(vr) ⊆ v1, . . . , vr−1. Hvis vi ∈ Γ(vr) far vi en anden længste vej i G ved

v1 · · · vivr · · · vi+1.

Vejen v1 · · · vivr · · · vi+1 kaldes da en simpel transformation af a.En vej b kaldes en transformation af vejen a, hvis b kan fas fra a ved en serie af simple trans-

formationer.

Sætning 4.5 Lad k ≥ 2 og lad G være en graf med n knuder hvori alle kredse har længde k ellermindre. Da er

e(G) ≤ k

2(n− 1).

Der gælder lighedstegn hvis og kun hvis G er sammenhængende og alle blokke er komplette graferaf orden k.

Et eksempel pa en sadan ekstremal graf (med K4-blokke) ses i figur 3.

20

Figur 3: En ekstremal graf med 19 knuder og kredse af længde højst 4.

Bevis. Vi anvender induktion efter antallet af knuder n. For n ≤ k gælder

e(G) ≤(n

2

)=n(n− 1)

2≤ k

2(n− 1).

Her gælder kun lighedstegn hvis n = 1 eller n = k og e(G) =(n2

), dvs. at G ' K1 eller G ' Kk.

Antag nu at n > k.6 Lad y1 · · · yr være en vilkarlig vej af maksimal længde i G; da ved vi (jf.definition 4.4) at Γ(yr) ⊆ y1, . . . , yr−1. Antag for modstrid at ys ∈ Γ(yr) med s ≤ r − k. Da erysys+1 · · · yr en kreds af længde r − s+ 1 ≥ k + 1 i G. Denne modstrid fortæller os at

Γ(yr) ⊆ yr−k+1, . . . , yr−1. (4.1)

Ved en simpel transformation af y1 · · · yr er det saledes kun yr−k+2, . . . , yr der kan bytte pladsi vejen. Alle knuderne y1, . . . , yr−k+1 er altsa fastholdt i enhver simpel transformation af vejeny1 · · · yr.

Vi betragter nu en specifik længste vej x1 · · ·xr i G, og arbejder i det følgende udelukkende medtransformationer af x1 · · ·xr. Lad M = xr−k+1, . . . , xr, og lad m = |M |. For r ≤ k, er M blotx1, . . . , xr; sa vi har m = min(k, r).

Af ovenstaende følger at x1, . . . , xr−k+1 er fastholdt i enhver transformation y1 · · · yr af x1 · · ·xr,dvs. yi = xi for alle 1 ≤ i ≤ r − k + 1. Lad L være mængden af endepunkter for transformationeraf x1 · · ·xr. Der gælder dermed L ⊆M , samt Γ(v) ⊆M for alle v ∈ L ifølge (4.1).

Sæt l = |L| og s = maxv∈L d(v). Lad v ∈ L være vilkarlig; da findes en transformation y1 · · · yrmed yr = v. For enhver nabo yi ∈ Γ(v) til v = yr, fas en simpel transformation af y1 · · · yr medyi+1 som endepunkt. Da en simpel transformation af y1 · · · yr igen er en transformation af x1 · · ·xr,følger at yi+1 ∈ L for alle yi ∈ Γ(v). Dermed er d(v) ≤ l; og da v ∈ L var vilkarlig, fas s ≤ l.

For enhver knude v ∈ L sætter vi nu av = e(v, L), dvs. antal kanter fra v til knuder i L.Tilsvarende sætter vi bv = e(v,M \ L). Antallet af kanter internt mellem knuderne i L og antalletaf kanter fra knuderne i L til knuder i M \ L bliver da hhv.

e(L) =12

∑v∈L

av, e(L,M \ L) =∑v∈L

bv.

Da Γ(v) ⊆M for alle v ∈ L, ser vi at der ma gælde

e(G)− e(G− L) = e(L) + e(L, V \ L) = e(L) + e(L,M \ L)

= 12

∑v∈L

av +∑v∈L

bv =∑v∈L

(12av + bv) . (4.2)

6I hintet til opgave 39.+ (side 139 i [BB]) deles op efter om δ(G) ≤ k2. Denne opdeling er dog unødvendig som

vores bevis demonstrerer.

21

For alle v ∈ L ved vi om av og bv at

bv ≤ |M \ L| = |M | − |L| = m− l ≤ k − l, av + bv = d(v) ≤ s ≤ l.

Dermed far vi for ethvert v ∈ L:

12av + bv = 1

2(av + bv) + 12bv ≤

12 l + 1

2(k − l) = 12k.

Indsætter vi nu denne vurdering i (4.2), far vi

e(G)− e(G− L) =∑v∈L

(12av + bv) ≤

∑v∈L

k

2=k

2l.

Da G−L indeholder n− l < n knuder (hvor n− l ≥ n− k > 0), far vi per induktion at e(G−L) ≤k2 (n− l − 1); og dette giver som ønsket

e(G) = (e(G)− e(G− L)) + e(G− L) ≤ k

2l +

k

2(n− l − 1) =

k

2(n− 1).

Antag nu at der gælder lighedstegn for G i uligheden, dvs. e(G) = k2 (n−1). I alle de vurderinger

vi har foretaget ovenfor, ma der saledes gælde lighed. Vi far altsa at der ogsa gælder lighedstegn foruligheden med G−L, og per induktion er G−L sammenhængende med blokke der alle er isomorfemed Kk. Desuden gælder |M | = m = k, og for alle v ∈ L er bv = k − l og av + bv = d(v) = s = l.Idet bv = k − l for v ∈ L, ma v være forbundet til alle knuder i M \ L.

Antag for modstrid at k − l > 1, dvs. at der findes x, y ∈ M \ L med x 6= y. Vælg et v ∈ L;da er v nabo til bade x og y. Da G − L er sammenhængende findes en vej π fra x til y i G − L.Lad z være den første knude pa denne vej der ligger i samme blok som y i G − L (vi kan godt

have z = x). Vejen π deles da i to stykker x π′−→ zπ′′−→ y. Knuden før y pa vejen vil altid ligge i

samme blok som y (vejens sidste kant er med i en blok), sa vi har i hvert fald z 6= y. Da blokken iG−L der indeholder z og y er Kk, kan π′′ erstattes med en vej τ af længde k− 1 fra z til y via alleblokkens knuder. Den samlede vej π′τ fra x til y har da længde mindst k − 1. Men i sa fald udgørπ′τ sammen med v en kreds af længde mindst k + 1 i G.

Mængden M \L indeholder altsa højst en knude, men da xr−k+1 er fastholdt i alle transforma-tioner, er xr−k+1 ∈ M \ L, sa M \ L = xr−k+1. Da bv = k − l = 1 for alle v ∈ L, er alle v ∈ Lforbundet til xr−k+1. Desuden er av = l− bv = l− 1 for v ∈ L, sa alle knuderne i L er forbundet tilalle andre knuder i L. Vi har dermed at alle knuder i M er forbundet til hinanden, sa M udgør etkomplet eksemplar af Kk.

Knuden xr−k+1 er forbindelsesled mellem M og den sammenhængende delgraf G − L, sa G ersammenhængende. Omvendt er xr−k+1 den eneste forbindelse mellem M = L∪ xr−k+1 og G−L(da knuderne i L kun er forbundet til knuder i M), sa xr−k+1 er en snitknude i G. Blokkene i G erderfor M samt alle blokkene i G− L, og alle disse blokke er isomorfe med Kk.

Ved induktion efter antallet af blokke ses at alle grafer med n knuder hvis blokke alle er Kk, hark2 (n − 1) kanter. Lad G være en graf hvor alle blokke er Kk. En kreds i G er 2-sammenhængendeog derfor indeholdt i en blok. Denne blok er isomorf med Kk, sa kredsen har længde højst k. Herafslutter vi at enhver graf der kun har Kk-blokke, faktisk er ekstremal.

22

Figur 4: Grafen B – butterfly-grafen.

4.3 Grafer uden “butterflies”

Lad B være grafen bestaende af to trekanter der netop har en knude til fælles. Grafen B er vist ifigur 4.

Vi vil nu bestemme EX(n;B) og ex(n;B) for alle n ≥ 5 (da “butterfly-grafen” B har 5 knuderer det kun interessant hvis n ≥ 5). Vi lader H1(n) og H2(n) være T2(n) med en kant tilføjet tilden mindste hhv. største af knudeklasserne. Hvis n er lige er H1(n) = H2(n). Bemærk at H1(n) ogH2(n) ikke er bipartite. Vi kalder knudeklasserne arvet fra T2(n) for “knudeklasserne i Hi(n)” –der er altsa en kant imellem to knuder i den ene af knudeklasserne i Hi(n). Ved at vise det følgenderesultat har vi vist at ex(n;B) = t2(n) + 1, og vi har dermed løst opgave 20.+ i [BB]. Den gar udpa at vise at en graf med n knuder og

⌊n2

4

⌋+ 2 kanter indeholder B, og ifølge bemærkning 2.6 er

t2(n) =⌊n2

4

⌋.

Sætning 4.6

EX(n;B) =H1(5), H2(5),K, n = 5H1(n), H2(n), n > 5,

hvor K er grafen vist i figur 5(c).

Bevis. Det ses at enhver af de pastaede ekstremale grafer Hi(n) ikke indeholder B, da alle trekanteri Hi(n) vil have kanten hvis endeknuder er i samme knudeklasse, til fælles. Herefter ses det at deer maksimale, altsa at man ikke kan tilføje en kant til en af dem uden at den derved fremkomnegraf indeholder B. Ved inspektion ses det at gælde for grafen K. Nu vises det for Hi(n):

Ved at tilføje en kant til H1(n) eller H2(n) fas en graf som er T2(n) tilføjet to kanter. Hvis B er endelgraf i alle grafer som fremkommer ved at tilføje to kanter til T2(n), ma H1(n) og H2(n) altsa væremaksimale. Lad knuderne i T2(n) være delt op i de to klasser V = v1, . . . , vr og W = w1, . . . , ws,sadan at r =

⌊n2

⌋og s =

⌈n2

⌉og sa kanterne er viwj | i = 1, . . . r, j = 1, . . . , s. Lad e og f

være to kanter som T2(n) ikke indeholder, og lad L = T2(n) + e+ f . Vi betragter først det tilfældeat e og f er kanter mellem knuder i hver knudeklasse. Uden tab af generalitet kan vi antage ate = v1v2 og f = w1w2. I sa fald er B en delgraf i L[v1, v2, w1, w2, w3] med trekanterne v1v2w3 ogw1w2v1 (der er mindst 3 knuder i W , da n ≥ 5). I det andet tilfælde kan vi antage at bade e og f erkanter mellem knuder i W . Hvis de har en knude til fælles kan vi antage at e = w1w2 og f = w2w3.Da udspændes B af knuderne w1, w2, w3, v1, v2 i L med trekanterne w1w2v1 og w2w3v2. Ellerskan vi antage at e = w1w2 og f = w3w4, og i sa fald er B en delgraf i L[w1, w2, w3, w4, v1] medtrekanterne w1w2v1 og w3w4v1.

I figur 5 er vist de 4 grafer med 5 knuder og 7 kanter, og ved inspektion ses at kun grafen i figur5(d) indeholder B (indikeret med røde kanter). De øvrige er de pastaede grafer i EX(5;B).

23

(a) Grafen H1(5). (b) Grafen H2(5). (c) Grafen K. (d) Graf med B.

Figur 5: De 4 ikke-isomorfe grafer med 5 knuder og 7 kanter.

(a) (b) (c) (d) (e) (f) (g) (h) (i)

(j) (k) (l) (m) (n) (o)

Figur 6: De 15 ikke-isomorfe grafer med 6 knuder og 10 kanter.

De 15 grafer med 6 knuder og 10 kanter er vist i figur 6. Det ses at kun grafen i figur 6(l) ikkeindeholder B, og at den netop er H1(6). Altsa er pastanden godtgjort for n = 6. Disse udtømmendelister af grafer har vi fra [FH] s. 217 og 223.

Nu vises pastanden for n ≥ 7 ved induktion, ved at antage pastandens rigtighed for n − 1. Vibenytter følgende vigtige egenskab ved H2(n) der gælder da H2(n) er fremkommet ved at tilføje enkant mellem knuder af minimal valens i T2(n):

δ(H2(n)) + 1 ≥ ∆(H2(n)). (4.3)

Induktionsskridtet er inspireret af det 3. bevis for Turans sætning i [BB]. Det bevis benytter netopat δ(Tr(n)) + 1 ≥ ∆(Tr(n)).

Antag at G har n knuder og bn2

4 c + 1 kanter, og at G ikke indeholder B. Vi vil nu vise atG ∈ H1(n), H2(n). Da G derved er maksimal ma vi sa have EX(n;B) = H1(n), H2(n) (vi kannemlig ikke have en graf P med endnu flere kanter som ikke indeholder B, da en delgraf af P medn knuder og t2(n) + 1 kanter ville være maksimal).

Fra (4.3) følger

δ(G) ≤ δ(H2(n)) ≤ ∆(H2(n)) ≤ ∆(G).

Lad g og h være knuder i hhv. G og H2(n) af minimal valens. Knuden h kan ikke være endeknudefor kanten der gar mellem to knuder i samme knudeklasse, og h er en knude i den største knudeklassei H2(n). Derfor ses at H2(n)− h ' H1(n− 1) eller H2(n)− h ' H2(n− 1). Vi har da

e(G− g) = e(G)− d(g) ≥ e(H2(n))− d(h) = e(H2(n)− h) = ex(n− 1, B).

Da G− g er en graf med n−1 knuder som ikke indeholder B har vi nu fra induktionsantagelsenat G− g ' H1(n− 1) eller G− g ' H2(n− 1). Antag først at G− g ' H1(n− 1).

24

Nu vises det at g ikke kan have kanter til begge knudeklasser i G − g. Lad V være den lilleknudeklasse og W den store/den anden i G− g, og lad e være kanten mellem to knuder i V . Antagfor modstrid at v1g, gw1 ∈ E(G), hvor v1 ∈ V og w1 ∈ W , og lad desuden w2 ∈ W være en andenknude i W . Antag først at e har en knude til fælles med kanten v1g, vi kan skrive e = v1v2. Sa erB en delgraf i G[v1, v2, g, w1, w2] med trekanterne v1gw1 og v1v2w2. Hvis derimod e = v2v3 harvi at B er delgraf i G[v1, v2, v3, g, w1] med trekanterne v1gw1 og v2v3w1. Derfor følger at g kunhar kanter til knuder i en af knudeklasserne i G− g.

Vi har

d(g) = e(G)− e(G− g) =⌊n2

4

⌋+ 1−

(⌊(n− 1)2

4

⌋+ 1)

=⌊n

2

⌋,

hvilket ses ved at dele op i tilfælde efter om n er lige eller ulige. Hvis n er lige har vi |V | =⌊n−1

2

⌋=

n2 − 1 og |W | =

⌈n−1

2

⌉= n

2 , sa V er for lille til at g kan være forbundet udelukkende til knuder i V .Dermed ma g være forbundet med alle knuderne i W , sa G ' H1(n) ' H2(n), med knudeklasserneW og V ∪ g. Hvis n er ulige er |V | = |W | =

⌊n−1

2

⌋=⌈n−1

2

⌉=⌊n2

⌋, sa g kan være forbundet til

alle knuderne i enten V eller W . Hvis g er forbundet til alle knuder i V er G ' H1(n), og ellers erG ' H2(n).

Antag nu at G− g ' H2(n− 1). Vi kan antage at n er lige, da i det andet tilfælde H2(n− 1) 'H1(n − 1), som er behandlet ovenfor. Ligesom før indses det at g ikke kan have kanter til beggeknudeklasserne i G− g. Herefter følger det ogsa som ovenfor at g er forbundet til alle knuder i denstørste knudeklasse i G− g, og at vi har G ' H1(n) ' H2(n). Dermed er det ønskede vist.

25

5 Szemeredis regularitetslemma

Szemeredis regularitetslemma er et meget kraftigt redskab til at bevise en lang række resultaterinden for flere forskellige matematiske omrader. En tidlig version af regularitetslemmaet blev ud-viklet af Endre Szemeredi (f. 1940) til at vise Szemeredis sætning i talteori. I dette projekt vil videsværre kun antydningsvist kunne illustrere hvorledes regularitetslemmaet kan bruges i ekstremalgrafteori, og dette er formalet med afsnit 6.

Szemeredis regularitetslemma er ogsa en interessant sætning i sig selv. Meget løst sagt sigersætningen at knuderne i enhver graf med tilstrækkeligt mange knuder kan inddeles i et begrænsetantal lige store klasser, sa kanterne mellem næsten alle par af to klasser er jævnt fordelt i en visforstand. Med dette menes at antallet af kanter mellem delmængder af de to klasser er omtrentproportionalt med antallet af knuder i delmængderne.

Dette præciseres i følgende definition af ε-regulære knudepartitioner:

Definition 5.1 Lad G = (V,E) være en graf, n = |V |, og (X,Y ) et par af disjunkte delmængder afV . Lad e(X,Y ) = eG(X,Y ) være antallet af X–Y -kanter.

Tallet d(X,Y ) = dG(X,Y ) = e(X,Y )|X||Y | kaldes densiteten af parret (X,Y ).

Vi kalder (X,Y ) et ε-regulært par hvis

|d(X ′, Y ′)− d(X,Y )| < ε (5.1)

for alle delmængder X ′ ⊆ X og Y ′ ⊆ Y med |X ′| ≥ ε|X| og |Y ′| ≥ ε|Y |. Hvis ε = 0 skal der “kun”gælde ≤ i (5.1).

En klassedeling (Ci)ki=0 af knudemængden V kaldes en ensartet partition hvis |C1| = |C2| =. . . = |Ck|. C0 kaldes undtagelsesklassen.

En klassedeling P = (Ci)ki=0 af knudemængden V kaldes en ε-regulær partition (med undtagel-sesklasse C0) hvis P er en ensartet partition med undtagelsesklasse C0, |C0| ≤ εn og højst εk2 afparrene (Ci, Cj) ikke er ε-regulære, 1 ≤ i < j ≤ k.

Par og partitioner der ikke er ε-regulære, kaldes ε-irregulære.

Bemærkning 5.2 Densiteten d(X,Y ) er forholdet mellem antallet af X–Y -kanter i G og antalletaf kanter i den komplette bipartite graf med knudeklasserne X og Y . Altsa er 0 ≤ d(X,Y ) ≤ 1.

Bemærkning 5.3 Et ε-regulært par (X,Y ) ses at være ε′-regulært for alle ε′ ≥ ε. Tilsvarende eren ε-regulær partition ogsa ε′-regulær for alle ε′ ≥ ε.

Lemma 5.4 Lad X og Y være disjunkte knudeklasser i en graf G. Antag at X ′ ⊆ X og Y ′ ⊆ Yopfylder |X ′| ≥ (1− γ)|X| > 0 og |Y ′| ≥ (1− δ)|Y | > 0. Sa gælder

|d(X ′, Y ′)− d(X,Y )| ≤ γ + δ (5.2)

og

|d2(X ′, Y ′)− d2(X,Y )| ≤ 2(γ + δ). (5.3)

Bevis. Vi ser først

0 ≤ e(X,Y )− e(X ′, Y ′) = e(X \X ′, Y \ Y ′) + e(X ′, Y \ Y ′) + e(X \X ′, Y ′)≤ (|X| − |X ′|)(|Y | − |Y ′|) + |X ′|(|Y | − |Y ′|) + (|X| − |X ′|)|Y ′|= |X||Y | − |X ′||Y ′| ≤ |X||Y | − (1− γ)|X|(1− δ)|Y |= (γ + δ − γδ)|X||Y | < (γ + δ)|X||Y |.

26

Sa har vi

d(X,Y )− d(X ′, Y ′) =e(X,Y )|X||Y |

− e(X ′, Y ′)|X ′||Y ′|

≤ e(X,Y )− e(X ′, Y ′)|X||Y |

< γ + δ. (5.4)

Hvis A og B er to mængder af knuder i G, sa har vi i komplementærgrafen G

dG(A,B) =eG(A,B)|A||B|

=|A||B| − eG(A,B)

|A||B|= 1− dG(A,B).

Derfor har vi, ved at bruge (5.4) for G i stedet for G,

dG(X ′, Y ′)− dG(X,Y ) = (1− dG(X ′, Y ′))− (1− dG(X,Y )) = dG(X,Y )− dG(X ′, Y ′) < γ + δ,

hvilket sammen med (5.4) beviser (5.2).Da densiteter højst er 1 fas

|d2(X ′, Y ′)− d2(X,Y )| = |d(X ′, Y ′) + d(X,Y )||d(X ′, Y ′)− d(X,Y )| < 2(γ + δ),

hvilket beviser (5.3).

Lemma 5.5 Lad (di)si=1 ∈ Rs, 1 ≤ t < s, D = 1s

∑si=1 di og d = 1

t

∑ti=1 di.

Sa er

1s

s∑i=1

d2i ≥ D2 +

t

s− t(D − d)2 ≥ D2 +

t

s(D − d)2.

Bevis. Vi bruger Jensens ulighed for den konvekse funktion x 7→ x2:

s∑i=1

d2i =

t∑i=1

d2i +

s∑i=t+1

d2i = t

(1t

t∑i=1

d2i

)+ (s− t)

(1

s− t

s∑i=t+1

d2i

)

≥ td2 + (s− t)

(1

s− t

s∑i=t+1

di

)2

= td2 + (s− t)(sD − tds− t

)2

= sD2 +st

s− t(D − d)2,

hvoraf det ønskede følger.

Definition 5.6 Givet en graf G og en ensartet partition P = (Ci)ki=0 med undtagelsesklasse C0

defineres kvadratgennemsnittet af P ved

q(P) =1k2

∑1≤i<j≤k

d2(Ci, Cj).

Vi ser at 0 ≤ d2(Ci, Cj) ≤ 1, sa da der er(k2

)led i summen fas

q(P) ≤ 1k2

k(k − 1)2

<12.

27

Følgende lemma er det store redskab i beviset for Szemeredis regularitetslemma. Lemma 5.7siger at hvis vi for en graf G har en ensartet, men ε-irregulær partition P med k + 1 klasser ogmindst εk2 par af klasser der er ε-irregulære, og hvor klasserne er tilstrækkeligt store, sa findes enanden ensartet partition P ′ med undtagelsesklasse C ′0 sadan at q(P ′) er betragteligt større end q(P)mens |C ′0| kun er lidt større end |C0|. Ideen i beviset for Szemeredis regularitetslemma er sa at vived gentagne gange at erstatte en ensartet, men ε-irregulær partition med en anden partition derhar højere kvadratgennemsnit, pa et tidspunkt ma fa en ε-regulær partition, da vi ellers ville fa enpartition med et kvadratgennemsnit over 1

2 . Lemma 5.7 og det efterfølgende bevis for Szemeredisregularitetslemma bygger pa fremstillingen i [BB] afsnit IV.5.

Lemma 5.7 Lad G = (V,E) være en graf med n = |V | knuder samt en ensartet partition P =(Ci)ki=0 med undtagelsesklasse C0 hvor |C0| ≤ εn og

|C1| = |C2| = . . . = |Ck| = c ≥ 23k+1.

Antag at P er ε-irregulær (sa mindst εk2 par (Ci, Cj) er ε-irregulære), hvor 0 < ε < 12 og

2−k ≤ ε5

8 . Sa findes en ensartet partition P ′ = (C ′i)`i=0 med ` = k(4k − 2k−1) og undtagelsesklasse

C ′0 ⊇ C0 sa

|C ′0| ≤ |C0|+n

2k

og

q(P ′) > q(P) +ε5

2.

Bevis. Lad H = 4k − 2k−1. Vi vil inddele hver klasse Ci i H klasser Dih, h = 1, . . . ,H, af ensstørrelse. Disse mindre klasser skal være klasserne i vores nye ensartede partition P ′. Bidraget fraparret (Ci, Cj) til kvadratgennemsnittet q(P ′) er i sa fald

H∑u=1

H∑v=1

d2(Diu, Djv). (5.5)

Vi vil vise hvordan man kan inddele Ci-klasserne sadan at bidragene fra de par (Ci, Cj) der erε-irregulære, er sa store at q(P ′) > q(P) + ε5

2 .For et par (Ci, Cj), 1 ≤ i < j ≤ k, som er ε-irregulært, lader vi Cij ⊆ Ci og Cji ⊆ Cj være

delmængder som viser ε-irregulariteten: |Cij | ≥ ε|Ci| = εc, |Cji| ≥ ε|Cj | = εc og

|d(Cij , Cji)− d(Ci, Cj)| ≥ ε. (5.6)

For et ε-regulært par (Ci, Cj) sætter vi blot Cij = Cji = ∅.For en given knudeklasse Ci betragter vi ækvivalensklasserne af knuder i Ci for følgende ækviva-

lensrelation ∼: v ∼ w hvis vi for alle j ≥ 1, j 6= i har v ∈ Cij ⇔ w ∈ Cij . Til hver ækvivalensklasseA svarer delmængden NA = Cij | A ⊆ Cij af mængden M = Ci1, . . . , Ci,i−1, Ci,i+1, . . . , Cik,sadan at elementerne i ækvivalensklassen A alle er indeholdt i alle Cij ∈ NA og i ingen Cij /∈ NA.Der kan højst være 2k−1 ækvivalensklasser, da der er 2k−1 delmængder af mængden M .

Sæt d =⌊c

4k

⌋. Sa er d ≥

⌊23k+1

22k

⌋= 2k+1. Da d ≤ c

4k har vi 4kd ≤ c og da d > c4k − 1 har vi

c < 4k(d+ 1), sa vi har

4kd ≤ c ≤ 4k(d+ 1)− 1. (5.7)

28

Vi lader nu Dih, h = 1, . . . ,H, være indbyrdes disjunkte delmængder af Ci pa d knuder hver, sadanat hver af mængderne Dih er indeholdt i en ∼-ækvivalensklasse. Alle elementer panær højst d− 1i hver ækvivalensklasse kan fordeles i disjunkte delmængder af størrelse d. Der findes mindst Hsadanne disjunkte mængder, da der er højst 2k−1 ækvivalensklasser, og (5.7) giver

Hd = 4kd− 2k−1d < c− 2k−1(d− 1) = |Ci| − 2k−1(d− 1).

For i = 1, . . . , k lader vi nu Ci =⋃Hh=1Dih, og for j = 1, . . . , k, j 6= i, sættes Cij =

⋃Dih⊆Cij

Dih.Vi har da fra (5.7)

|Ci \ Ci||Ci|

=c−Hd

c≤ 4k(d+ 1)− 1− (4k − 2k−1)d

4kd<

4k + 2k−1d

4kd=

1d

+1

2k+1.

Da d ≥ 2k+1 fas

|Ci \ Ci||Ci|

<2

2k+1= 2−k ≤ ε5

8, (5.8)

hvor vi til sidst har brugt betingelsen 2−k ≤ ε5

8 . Det giver |Ci| − |Ci| = |Ci \ Ci| ≤ ε5

8 |Ci|, sa|Ci| ≥ (1− ε5

8 )|Ci|. Vi har nu fra lemma 5.4 at

|d(Ci, Cj)− d(Ci, Cj)| ≤ 2ε5

8=ε5

4, (5.9)

og

|d2(Ci, Cj)− d2(Ci, Cj)| ≤ε5

2(5.10)

for 1 ≤ i < j ≤ k.Da er

1k2

∑1≤i<j≤k

d2(Ci, Cj) ≥1k2

∑1≤i<j≤k

(d2(Ci, Cj)−

ε5

2

)=

1k2

∑1≤i<j≤k

d2(Ci, Cj)−1k2

(k

2

)ε5

2

>1k2

∑1≤i<j≤k

d2(Ci, Cj)−ε5

4. (5.11)

Antag fra nu af at (Ci, Cj) er et ε-irregulært par. Da enhver af klasserne Dih enten er disjunktmed Cij eller helt indeholdt i Cij , ma Cij \ Cij ⊆ Ci \ Ci. Sa far vi, ved at bruge (5.8),

|Cij \ Cij ||Cij |

≤ |Ci \ Ci|ε|Ci|

≤ ε4

8. (5.12)

Vi har ogsa, ved at bruge (5.8) hvor vi har ganget igennem med |Ci|,

|Cij | ≥ |Cij | − |Ci \ Ci| ≥ (ε− ε5

8)|Ci| = (1− ε4

23)ε|Ci| ≥ (1− 1

27)ε|Ci|,

hvor vi til sidst har brugt ε < 12 .

29

Det giver os

|Cij ||Ci|

≥ (1− 127

)ε. (5.13)

Pa samme made som da vi udledte (5.9), fas nu fra (5.12) og lemma 5.4

|d(Cij , Cji)− d(Cij , Cji)| ≤ε4

4. (5.14)

Ved at bruge trekantsuligheden to gange fas

|d(Cij , Cji)− d(Ci, Cj)| ≤ |d(Cij , Cji)− d(Cij , Cji)|+ |d(Cij , Cji)− d(Ci, Cj)|+ |d(Ci, Cj)− d(Ci, Cj)|,

sa da (Ci, Cj) er et ε-irregulært par, fas af (5.6), (5.9) og (5.14)

|d(Cij , Cji)− d(Ci, Cj)| ≥ |d(Cij , Cji)− d(Ci, Cj)|− |d(Cij , Cji)− d(Cij , Cji)| − |d(Ci, Cj)− d(Ci, Cj)|

≥ ε− ε4

4− ε5

4> ε− ε

25− ε

26=

6164ε >

1516ε. (5.15)

Vi vil gerne benytte lemma 5.5 til at finde en nedre grænse for bidraget (5.5) til kvadratsummenq(P ′) fra de klasser i P ′ der er indeholdt i det ε-irregulære par (Ci, Cj). Sæt derfor

X =1H2

H∑u=1

H∑v=1

d(Diu, Djv) =1H2

H∑u=1

H∑v=1

e(Diu, Djv)|Diu||Djv|

=1

d2H2

H∑u=1

H∑v=1

e(Diu, Djv) =e(Ci, Cj)∣∣Ci∣∣ ∣∣Cj∣∣ = d(Ci, Cj),

da Ci netop er en forening af de H klasser Dih for h = 1, . . . ,H af størrelse d (tilsvarende for Cj).Lad A(Cij) = u ∈ 1, . . . ,H | Diu ⊆ Cij. Vi definerer desuden

x =1

|A(Cij)||A(Cji)|

∑u∈A(Cij)

∑v∈A(Cji)

d(Diu, Djv) =1

|A(Cij)||A(Cji)|

∑u∈A(Cij)

∑v∈A(Cji)

e(Diu, Djv)|Diu||Djv|

=1

d2|A(Cij)||A(Cji)|

∑u∈A(Cij)

∑v∈A(Cji)

e(Diu, Djv) =e(Cij , Cji)|Cij ||Cji|

= d(Cij , Cji).

Lemma 5.5 giver nu med (dw)H2

w=1 = (d(Diu, Djv))1≤u,v≤H den følgende ulighed7

1H2

H∑u=1

H∑v=1

d2(Diu, Djv) ≥ X2 +|A(Cij)||A(Cji)|

H2(X − x)2

= d2(Ci, Cj) +d2|A(Cij)||A(Cji)|

d2H2(d(Ci, Cj)− d(Cij , Cji))2

= d2(Ci, Cj) +|Cij ||Cji||Ci||Cj |

(d(Ci, Cj)− d(Cij , Cji))2.

7I følgende vurdering star der i [BB] fejlagtigt|Cij ||Cji||Ci||Cj |

i stedet for|Cij ||Cji||Ci||Cj |

.

30

Fra (5.13) og (5.15) fas nu for det ε-irregulære par (Ci, Cj)

1H2

H∑u=1

H∑v=1

d2(Diu, Djv) > d2(Ci, Cj) +((1− 2−7)ε

)2(1516ε

)2

= d2(Ci, Cj) +2857532768

ε4

> d2(Ci, Cj) +34ε4. (5.16)

Vi ophører nu med at betragte et specifikt ε-irregulært par. For et (muligvis ε-regulært) par(Ci, Cj) har vi fra Jensens ulighed med den konvekse funktion x 7→ x2

1H2

H∑u=1

H∑v=1

d2(Diu, Djv) ≥

(1H2

H∑u=1

H∑v=1

d(Diu, Djv)

)2

=

(1

d2H2

H∑u=1

H∑v=1

e(Diu, Djv)

)2

= d2(Ci, Cj). (5.17)

Vi lader nu C ′1, . . . , C ′` = Dih | i = 1, . . . , k, h = 1, . . . ,H, ` = H · k og C ′0 =V \

⋃`j=1C

′j . Endelig defineres den nye partition P ′ = (C ′j)

`j=0. Det skal nu tjekkes at P ′ har

de ønskede egenskaber.Vi har C ′0 ⊇ C0, sa fra første ulighed i (5.8), hvor vi har ganget igennem med |Ci|, fas den

ønskede øvre grænse for |C ′0|:

|C ′0| = |C0|+ |C ′0 \ C0| = |C0|+k∑i=1

|Ci \ Ci| ≤ |C0|+k∑i=1

2−k|Ci| = |C0|+ 2−kkc ≤ |C0|+n

2k.

Nu bestemmes en nedre grænse for kvadratgennemsnittet q(P ′). Da der er mindst εk2 par(Ci, Cj) som er ε-irregulære fas fra (5.16) og (5.17)

q(P ′) =1`2

∑1≤i<j≤`

d2(C ′i, C′j) ≥

1(kH)2

∑1≤i<j≤k

H∑u=1

H∑v=1

d2(Diu, Djv)

=1k2

∑1≤i<j≤k

1H2

H∑u=1

H∑v=1

d2(Diu, Djv) >1k2

∑1≤i<j≤k

d2(Ci, Cj) +1k2· εk2 · 3

4ε4

>1k2

∑1≤i<j≤k

d2(Ci, Cj) +34ε5.

Ved at bruge (5.11) fas nu

q(P ′) > 1k2

∑1≤i<j≤k

d2(Ci, Cj)−ε5

4+

34ε5 = q(P) +

ε5

2,

hvilket var hvad vi ville vise.

Sætning 5.8 (Szemeredis regularitetslemma) For m ∈ N og 0 < ε < 12 findes et M = M(ε,m) ∈ N

sadan at alle grafer med mindst m knuder har en ε-regulær partition (Ci)ki=0 med m ≤ k ≤M .

31

Bevis. Sæt t =⌊ε−5⌋, og lad k0 være det mindste tal der opfylder k0 ≥ m og 2−k0 ≤ 1

8ε5.

Vi definerer desuden tallene k1, . . . , kt+1 rekursivt ved ki+1 = ki(4ki − 2ki−1). Vi pastar nu atM = kt23kt+2 opfylder kravene i Szemeredis regularitetslemma.

Lad G være en graf med n ≥ m knuder. Ved at dele knuderne op i singletonmængder Ci = vihvor v1, . . . , vn er knuderne i G, far vi med C0 = ∅ en 0-regulær partion (Ci)ni=0 idet alle par afsingletonklasser er 0-regulære. Da en 0-regulær partition er ε-regulær, far vi for n ≤M en ε-regulærpartition med det ønskede antal klasser. I det følgende antager vi derfor at n > M .

Lad P0 = (C(0)i )k0

i=0 være en ensartet partition (af knuderne i G) med∣∣∣C(0)

1

∣∣∣ = · · · =∣∣∣C(0)

k0

∣∣∣ =

bn/k0c. Da 2−k0 ≤ ε5/8 < ε, gælder

k02ε< k02k0+1 < kt23kt+2 = M < n.

Dermed opfylder undtagelsesklassen C(0)0 at

0 ≤∣∣∣C(0)

0

∣∣∣ = n− k0

⌊n

k0

⌋< n− k0

(n

k0− 1)

= k0 <ε

2n.

Af hensyn til det følgende bemærker vi at q(P0) ≥ 0 = 0 · ε5/2.Vi finder nu en efter en ensartede partitioner P1,P2, . . . ,Pt+1 indtil vi far en ε-regulær partition.

For 0 ≤ j ≤ t har partitionen Pj = (C(j)i )kj

i=0 egenskaberne∣∣∣C(j)

0

∣∣∣ ≤ ∣∣∣C(0)0

∣∣∣+ n(2−k0 + . . .+ 2−kj−1),

samt q(Pj) ≥ j(ε5/2).Hvis Pj er ε-regulær for et 0 ≤ j ≤ t, opfylder Pj betingelserne i Szemeredis regularitetslemma

idet Pj er en ε-regulær partition med kj ≤ kt ≤M klasser.Hvis Pj (med 0 ≤ j ≤ t) er ε-irregulær, vil vi vise eksistensen af Pj+1 ud fra lemma 5.7. Idet

2−k0 ≤ ε5/8 < 2−8, gælder k0 ≥ 8. Dermed er 4k0 > 2k0 > 2k0−1 + 2, sa k1 = k0(4k0 − 2k0−1) > 2k0.Undtagelsesklassen i Pj opfylder da at∣∣∣C(j)

0

∣∣∣ ≤ ∣∣∣C(0)0

∣∣∣+ n(2−k0 + 2−k1 + . . .+ 2−kj−1) ≤ ε

2n+ n(2−k0 + t2−k1)

<ε

2n+ n(2−k0 + t(2−k0)2) ≤ ε

2n+ n

(ε5

8+ ε−5

(ε5

8

)2)

≤ ε

2n+ n

(ε4

+ε

4

)= εn

Da ε < 12 , gælder for alle 1 ≤ i ≤ kj

∣∣∣C(j)i

∣∣∣ =n−

∣∣∣C(j)0

∣∣∣kj

≥ n

2kj≥ M

2kt= 23kt+1 ≥ 23kj+1.

Idet Pj er ε-irregulær, giver lemma 5.7 at der findes en ensartet partition Pj+1 = (C(j+1)i )kj+1

i=0

der opfylder

q(Pj+1) ≥ q(Pj) +ε5

2≥ j ε

5

2+ε5

2= (j + 1)

ε5

2,

samt ∣∣∣C(j+1)0

∣∣∣ ≤ ∣∣∣C(j)0

∣∣∣+ n2−kj ≤∣∣∣C(0)

0

∣∣∣+ n(2−k0 + · · ·+ 2−kj ).

32

Nu ma der gælde at en af partitionerne P0, . . . ,Pt er ε-regulær, for ellers vil Pt+1 eksistere med

q(Pt+1) ≥ (t+ 1)ε5

2> ε−5 ε

5

2=

12

i modstrid med at q(Pt+1) < 12 ifølge bemærkningen efter definition 5.6.

Nar n > M findes altsa en ε-regulær partition af G med mindst m og højst kt ≤M klasser.

Følgende lemma fortæller at for de fleste knuder a ∈ A i et ε-regulært par (A,B), er kanternefra a til B jævnt fordelt pa knuderne i B med densitet ca. d(A,B).

Lemma 5.9 Lad (A,B) være et ε-regulært par med densitet d = d(A,B) af knudeklasser i en graf,og lad Y ⊆ B opfylde |Y | ≥ ε|B|. Sa gælder

#a ∈ A | e(a, Y ) ≤ (d− ε)|Y | < ε|A|

og

#a ∈ A | e(a, Y ) ≥ (d+ ε)|Y | < ε|A|.

Bevis. Vi beviser kun den første ulighed. Den anden følger med helt analoge argumenter.Antag at det for en delmængde Y ⊆ B med |Y | ≥ ε|B| gælder

#a ∈ A | e(a, Y ) ≤ (d− ε)|Y | ≥ ε|A|.

Lad X = a ∈ A | e(a, Y ) ≤ (d− ε)|Y |. Sa er

d(X,Y ) =∑

x∈X e(x, Y )|X||Y |

≤ |X|(d− ε)|Y ||X||Y |

= d− ε,

sa |d(A,B)− d(X,Y )| ≥ ε. Dermed er (A,B) ikke et ε-regulært par, idet |X| ≥ ε|A|.

Lemma 5.10 Lad (A,B) være en ε-regulært par, og antag at α ≥ ε. Lad desuden A′ ⊆ A, |A′| ≥α |A|, og B′ ⊆ B, |B′| ≥ α |B|.

Da er parret (A′, B′) ε′-regulært med ε′ = max(ε/α, 2ε) og densiteten opfylder∣∣d(A′, B′)− d(A,B)∣∣ < ε.

Bevis. Lad ε, α, ε′, A, B, A′ og B′ være givet som i sætningen.Da α ≥ ε, er |A′| ≥ ε |A| og |B′| ≥ ε |B|, sa idet (A,B) er ε-regulært, fas∣∣d(A′, B′)− d(A,B)

∣∣ < ε.

Antag nu at X ⊆ A′ og Y ⊆ B′ med hhv. |X| ≥ ε′ |A′| og |Y | ≥ ε′ |B′|. For X (og tilsvarendefor Y ) gælder da

|X| ≥ ε′∣∣A′∣∣ ≥ ε

α

∣∣A′∣∣ ≥ ε |A| .For parret (X,Y ) gælder derfor∣∣d(X,Y )− d(A′, B′)

∣∣ ≤ |d(X,Y )− d(A,B)|+∣∣d(A,B)− d(A′, B)

∣∣ < ε+ ε ≤ ε′.

Parret (A′, B′) er saledes ε′-regulært.

33

Det kan være nyttigt at arbejde med en ε-regulær partition af knuderne i en graf, sadan at derikke er kanter mellem knuder i samme klasse, og sa alle par af knudeklasser enten ikke indeholderkanter eller er ε-regulære med densitet mindst d. Følgende sætning gør rede for at en sadan partitionkan konstrueres ved blot at fjerne “fa” kanter fra den oprindelige graf. Sætningen er anført i [KS]uden bevis, og vi har heller ikke kunnet finde et bevis andetsteds, sa beviset har vi selv konstrueret.

Sætning 5.11 (Valensform af Szemeredis regularitetslemma) For ε > 0 findes et M = M(ε) ∈ Nsadan at hvis G = (V,E) er en graf og d ∈ [0, 1], findes en ensartet partition C0, C1, . . . , Ck af Vog en delgraf G′ (med samme knudemængde som G) af G som opfylder følgende:

• k ≤M .

• |C0| ≤ ε |V |.

• Størrelsen af alle andre klasser er m ≤ dε |V |e.

• degG′(v) > degG(v)− (d+ ε) |V | for alle v ∈ V .

• e(G′[Ci]) = 0 for alle i > 0.

• Ethvert par af klasser (Ci, Cj) i G′, hvor 1 ≤ i < j ≤ k, er tomt eller ε-regulært med densitetstørre end d.

Bevis. Lad ε > 0 være givet. Alle betingelser i valensformen bliver strammere nar ε gøres mindre(bortset fra 1. og 5. betingelse der ikke ændres); vi kan derfor antage at ε < 1.

Sæt γ = ε2/16 og m0 = d4/εe. Szemeredis regularitetslemma giver da et M(γ,m0) ∈ N saenhver graf med mindst m0 knuder har en γ-regulær partition (C ′i)

ki=0 hvor m0 ≤ k ≤ M(γ,m0).

Vi pastar nu at vi i valensformen kan anvende M = M(γ,m0).Lad G være en graf med n knuder, og lad d ∈ [0, 1]. Vi ser først pa tilfældet n < m0, og

lader (Ci)ni=0 være singleton-partitionen med tom undtagelsesklasse. De første tre betingelser ivalensformen er opfyldt:

n < m0 ≤M, |C0| = 0 ≤ εn, |Ci| = 1 ≤ dεne for alle i ≥ 1.

Med G′ = G er de tre resterende egenskaber ogsa opfyldt idet der gælder

• For alle v ∈ V , er degG(v) > degG(v)− (d+ ε)n.

• For alle i ≥ 1, er e(G[Ci]) = 0.

• For alle 1 ≤ i < j ≤ n, er parret (Ci, Cj) i G 0-regulært med densitet 0 eller 1 ≥ d.

Antag nu at n ≥ m0, og lad (C ′i)k′i=0 være en γ-regulær partition med m0 ≤ k′ ≤M . Umiddelbart

far vi da at der gælder ∣∣C ′0∣∣ ≤ γn =ε2

16n ≤ ε

4n.

Da de n knuder fordeles ligeligt pa k′ klasser (samt en undtagelsesklasse), er der højst nk′ knuder i

en klasse, og saledes er ∣∣C ′1∣∣ = · · · =∣∣C ′k′∣∣ = m′ ≤ n

k′≤ n

m0≤ ε

4n.

34

Vi begynder nu at danne grafen G′ med den tilhørende ensartede partition. Strategien bagdannelsen af den nye partition er at flytte tilstrækkeligt mange “problematiske” knuder til und-tagelsesklassen. Pa denne made kan de problematiske knuder ignoreres nar vi senere skal dannedelgrafen G′ af G.

Som det første tager vi alle klasser C ′i der indgar i mere end ε4k′ par der er γ-irregulære, og alle

knuder i disse klasser føjes til undtagelsesklassen. Da partitionen er γ-regulær, er der højst γk′2 parder er γ-irregulære, og i hvert af disse par indgar to klasser. Hver af de udvalgte klasser indgar imindst ε

4k′ af disse par, sa der er højst

2γk′2ε4k′ =

2ε2k′2/16εk′/4

=ε

2k′

sadanne udvalgte klasser. Antallet af knuder der i denne operation flyttes til undtagelsesklassen ersaledes højst ε

2k′ ·m′ ≤ ε

2n.Lad C ′i være en af de resterende klasser. Vi ser da pa de lavdensitetspar (γ-regulære par med

densitet mindre end eller lig d + γ), som C ′i indgar i. Alle knuder i C ′i der for mere end ε4k′

lavdensitetspar (C ′i, C′j) har flere end (d+ 2γ)m′ kanter til C ′j , flyttes til undtagelsesklassen.

Lad A være antallet af par (v, C ′j) hvor v ∈ C ′i har mindst (d+ 2γ)m′ kanter til C ′j og (C ′i, C′j)

er et lavdensitetspar. Lemma 5.9 fortæller at for hvert lavdensitetspar (C ′i, C′j), er der højst γm′ af

knuderne i C ′i der har mere end (d+2γ)m′ kanter til C ′j . Desuden indgar C ′i i højst k′ lavdensitetspar.Samlet gælder altsa A ≤ k′ · γm′.

Da alle de flyttede knuder har “mange” kanter i mindst ε4k′ lavdensitetspar, far vi at antallet

af flyttede knuder fra C ′i højst er

Aε4k′ ≤

k′ · γm′ε4k′ =

k′m′ε2/16εk′/4

=ε

4m′.

For at sikre at der stadig er lige mange knuder i de resterende partitionsklasser (sa partitio-nen stadig er ensartet), flytter vi ekstra knuder til undtagelsesklassen fra de klasser hvorfra derblev fjernet fa knuder. Fra hver af de højst k′ resterende klasser er der altsa blevet fjernet ligemange, og højst ε

4m′ knuder. Samlet set er der altsa blevet tilføjet højst ε

4m′ · k′ ≤ ε

4n knuder tilundtagelsesklassen pa dette trin.

Kald den nye (forøgede) undtagelsesklasse for C0, og kald de udtyndede, resterende klasser forC1, . . . , Ck. Da er (Ci)ki=0 en ensartet partition der umiddelbart opfylder følgende egenskaber:

• k ≤ k′ ≤M .

• |C1| = · · · = |Ck| = m ≤ m′ ≤ ε4n.

• m ≥ m′ − ε4m′ > 3

4m′

• |C0| ≤ |C ′0|+ ε2n+ ε

4n ≤ εn.

For alle klassepar (Ci, Cj) der stammer fra et γ-regulært par i den gamle partition, giver lemma 5.10at (Ci, Cj) er 2γ-regulært, idet max( γ

3/4 , 2γ) = 2γ. Hvis (Ci, Cj) stammer fra et højdensitetspar(densitet større end d+ γ), giver lemmaet desuden at d(Ci, Cj) > d.

For alle i ≥ 1, indgar Ci altsa højst i ε4k′ par der er 2γ-irregulære. For alle i ≥ 1 og v ∈ Ci, findes

desuden højst ε4k′ lavdensitetspar (Ci, Cj) (med densitet højst d) hvori v har mere end (d+ 2γ)m′

kanter til Cj .

35

Indtil videre har vi kun flyttet rundt pa knuderne i den givne partition. Nu begynder vi dogat danne delgrafen G′ af G ved at fjerne kanter fra G. Alle kanter internt i klasserne C1, . . . , Ckfjernes. Fra en knude v 6∈ C0, fjernes pa denne made højst m kanter.

Alle kanter i 2γ-irregulære par fjernes. For i ≥ 1, indgar Ci i højst ε4k′ irregulære par, sa fra en

knude v ∈ Ci fjernes højst ε4k′ ·m ≤ ε

4n kanter pa dette trin.Alle kanter i lavdensitetspar (densitet højst d) fjernes. For en knude v ∈ Ci (i ≥ 1) vil der

for størstedelen af parrene (Ci, Cj) højst blive fjernet (d + 2γ)m′ kanter fra v. For op til ε4k′

lavdensitetspar (Ci, Cj) kan v dog have mere end (d+ 2γ)m′ kanter til Cj , og for disse par skal dersaledes fjernes op til m kanter fra v. Samlet set bliver der altsa pa dette trin højst fjernet

(d+ 2γ)m′ · k +m · ε4k′ ≤ (d+ 2γ)n+

ε

4n

kanter fra v.Nar alle disse kanter er fjernet, star vi tilbage med en delgraf G′ som opfylder at e(G′[Ci]) = 0

for alle i ≥ 1. Alle par (Ci, Cj) (med 1 ≤ i < j ≤ k) er desuden 2γ-regulære (og dermed ε-regulære),og et par er enten tomt eller har “høj” densitet (mere end d).

Til sidst bemærker vi om antallet degG(v) − degG′(v) af kanter der er fjernet fra en knude v:Det er 0 og dermed mindre end (d+ ε)n hvis v ∈ C0. Hvis v 6∈ C0, gælder

degG(v)− degG′(v) ≤ m+ε

4n+ (d+ 2γ)n+

ε

4n ≤ ε

4n+

ε

4n+

(d+

ε2

8

)n+

ε

4n < (d+ ε)n.

Partitionen (Ci)ki=0 og delgrafen G′ har dermed alle egenskaber pakrævet i valensformen, og k ≤k′ ≤M .

Bemærkning 5.12 Lad G′ være delgrafen man far hvis man anvender valensformen pa en graf Gmed n knuder. Typisk er man ikke interesseret i undtagelsesklassen C0, sa hvis vi fjerner C0 fra G′,far vi en delgraf G′′ af G der er særligt pæn. Alle klasser i G′′ har samme størrelse, og klassernehar ingen interne kanter. Ethvert par af klasser er enten tomt eller ε-regulært med høj densitet(densitet større end d). Grafen G′′ indeholder desuden stadig størstedelen af kanterne i G, idet vifor alle knuder v i G′′ har

degG′′(v) > degG(v)− (d+ ε)n− |C0| ≥ degG(v)− (d+ 2ε)n.

Dermed opfylder det samlede kantantal at

e(G′′) = 12

∑v∈V (G′′)

degG′′(v)

> 12

∑v∈V (G′′)

(degG(v)− (d+ 2ε)n) +∑v∈C0

(degG(v)− n)

≥ 1

2

∑v∈V (G)

degG(v)− (d+ 2ε)n2 − εn2

= e(G)− (d+ 3ε)

n2

2.

36

6 Anvendelse af Szemeredis regularitetslemma

I dette afsnit giver vi et eksempel pa hvordan man kan anvende Szemeredis regularitetslemma. Vigenbeviser Erdos-Stones sætning, dog i en svagerer udgave end sætning 3.6. Beviserne i dette afsnitbygger pa beviser fra [KS].

Definition 6.1 Givet en graf G = (V,E), en partition P af V i knudeklasser V1, . . . , Vk og toparametre ε, d definerer vi den reducerede graf R saledes: knuderne i R er knudeklasserne V1, . . . , Vk,og ViVj er en kant i R hvis (Vi, Vj) er et ε-regulært par i G med dG(Vi, Vj) > d.

Givet en graf S forstas ved S(t) for t ∈ N den graf der fas ved at erstatte enhver knudex ∈ V (S) med t uafhængige knuder Wx, og kantforbinde alle knuder i Wx med alle knuder i Wy

hvis xy ∈ E(S).

Lemma 6.2 (Nøglelemma) Lad d > ε > 0, en graf R og m ∈ N være givet. Vi lader for alle x ∈ V (R)Vx være m knuder og Exy for xy ∈ E(R) være en mængde af Vx–Vy-kanter sadan at (Vx, Vy) eret ε-regulært par med d(Vx, Vy) ≥ d. Vi konstruerer herved en graf G med V (G) =

⋃x∈V (R) Vx og

E(G) =⋃xy∈E(R)Exy. Lad H være en delgraf af R(t) med ∆ = ∆(H) > 0, og lad δ = d − ε og

ε0 = δ∆

2+∆ . Hvis ε ≤ ε0 og t− 1 ≤ ε0m, sa er H en delgraf af G.

Bevis. Vi antager at betingelserne i lemmaet er opfyldte, og angiver en algoritme som finder enindlejring af H i G. Lad V (H) = v1, . . . , vh. Ved placeringen af vi forstar vi den i indlejringen tilvi svarende knude, kald den ui ∈ V (G). Vi indlejrer knuderne i G ved at placere dem en efter en iden vilkarlige rækkefølge v1, . . . , vh, saledes at algoritmen pa det i’te trin fastlægger placeringen afvi. Nar algoritmens i’te trin afsluttes er Cij for j > i en mængde af knuder i G der vil indeholdeplaceringen af vj i den endelige indlejring. Knudeklasserne i R(t) betegner vi Wx, x ∈ V (R), somi definition 6.1. Lad knuden vj være indeholdt i Wx i R(t). Sa lader vi C0j = Vx, og har følgendekæde af inklusioner:

C0j ⊃ C1j ⊃ . . . ⊃ Cj−1,j ⊃ uj.

Nu beskriver vi hvad der foretages pa det i’te trin i algoritmen:

1) Placering af vi. Vi vælger ui ∈ Ci−1,i \ u1, . . . , ui−1 sa

e(ui, Ci−1,j) > δ|Ci−1,j | for alle j > i hvor vivj ∈ E(H). (6.1)

2) Definition af Cij for j > i. For alle j > i sætter vi

Cij =

Ci−1,j ∩ Γ(ui) hvis vivj ∈ E(H)Ci−1,j hvis vivj /∈ E(H).

For i < j lader vi dij = #` = 1, . . . , i | v`vj ∈ E(H). Vi ser dij ≤ ∆, da dij tælleren delmængde af naboknuderne til vj . Hvis v`vj ∈ E(H), ` < j, sættes i algortimens `’te trinC`j = C`−1,j ∩ Γ(u`), sa |C`j | = e(u`, C`−1,j) > δ|C`−1,j |. Dette sker for dij værdier af ` i løbet afalgoritmens første i trin. Hvis dij > 0 har vi dermed

|Cij | > δdij |C0j | = δdijm ≥ δ∆m >δ∆

2 + ∆m = ε0m ≥ εm.

37

Hvis dij = 0 har vi |Cij | = m > εm. Nar vi skal placere vi er der derfor for hvert j > ihvor vivj ∈ E(H) ifølge lemma 5.9 højst εm knuder w ∈ Ci−1,i der ikke opfylder e(w,Ci−1,j) >δ|Ci−1,j | = (d − ε)|Ci−1,j |. Da d(vi) ≤ ∆ er der altsa højst ∆εm knuder i Ci−1,i der ikke opfylder6.1. Der er desuden højst t− 1 knuder fra Ci−1,i som ogsa er i mængden u1, . . . , ui−1 af tidligereplaceringer, idet højst t− 1 knuder i H − vi er i den samme af knudeklasserne i R(t) som vi. Altsaer der mindst

|Ci−1,i| −∆εm− (t− 1) > δ∆m−∆εm− (t− 1) = (δ∆ −∆ε)m− (t− 1)

mulige placeringer af vi.Vi vurderer nu størrelsen af t− 1:

t− 1 ≤ ε0m =δ∆

2 + ∆m <

2δ∆

2 + ∆m =

(2 + ∆)δ∆ −∆δ∆

2 + ∆m =

(δ∆ −∆

δ∆

2 + ∆

)m

= (δ∆ −∆ε0)m ≤ (δ∆ −∆ε)m,

sa der er mindst 1 mulig placering af vi for alle 1 ≤ i ≤ h.

Bemærkning 6.3 Det er interessant at antallet af kanter e(H) ikke har nogen direkte betydningfor at vi kan finde H i G, nar ovenstaende metode benyttes. Det eneste der har betydning er denmaksimale knudevalens ∆ af H.

En made at anvende Szemeredis regularitetslemma pa er først at anvende valensformen pa engraf G, som beskrevet i bemærkning 5.12, sa en “ren” graf G′′ fas med tilhørende ε-regulær partitionfor et passende ε. Herefter betragtes den reducerede graf R. Pa denne graf, eller pa en udvidelseR(t) af R, anvendes nu et passende resultat i ekstremal grafteori, sa en bestemt delgraf pavises.Det kan, som vi nedenfor skal se, f.eks. være at pavise eksistensen af en komplet delgraf Kr i Rvha. Turans sætning. Herefter kan Nøglelemmaet bruges til at vise eksistensen af samme delgraf iG′′, og dermed ogsa i G.

Sætning 6.4 (Svag version af Erdos-Stone) Lad r ∈ N og 0 < ε < 1r . For alle t ∈ N findes da et

heltal N = N(r, ε, t) sa enhver graf G med n ≥ N knuder og

e(G) ≥ (1− 1r

+ ε)(n

2

)kanter indeholder Kr+1(t).

Bevis. Lad r, t ∈ N og 0 < ε < 1r være givet. Lad desuden G være en graf med n knuder og

e(G) ≥ (1− 1r + ε)

(n2

).

Sæt d = ε2 og γ = (ε/6)(r+1)t. Vi benytter nu valensformen af Szemeredis regularitetslemma

(vi bruger γ som ε i valensformen) og far en partition (Ci)ki=0 (hvor k ≤ M(γ)) af knuderne iG samt en delgraf G′ af G som opfylder betingelserne i valensformen. Ved efterfølgende at fjerneundtagelsesklassen C0 far vi fra bemærkning 5.12 en delgraf G′′ (med mindst n − γn knuder) deropfylder:

|C1| = · · · = |Ck| = m,

e(G′′) > e(G)−(ε

2+ 3

(ε6

)(r+1)t)n2

2,

e(G′′(Ci)) = 0 for alle i ≥ 1,

for 1 ≤ i < j ≤ k er dG′′(Ci, Cj) = 0 eller (Ci, Cj) er γ-regulær med dG′′(Ci, Cj) >ε

2.

38

Da alle de k klasser i G′′ har samme størrelse, opfylder det samlede antal knuder n′ i G′′ atn′ = mk ≥ (1− γ)n. Størrelsen af klasserne ma være nedadtil begrænset med

m =n′

k≥ 1− γM(γ)

n.

Da ε < 1, er ε/6− (ε/6)(r+1)t > 0. Dermed findes et N ′ ∈ N sa vi for n ≥ N ′ har

32n ·

(ε

6−(ε

6

)(r+1)t)>ε

2.

Ved at rykke lidt rundt pa leddene far vi

ε ·(n

2− 1

2

)>εn

4+ 3 · n

2

(ε6

)(r+1)t.

Ganger vi med n pa begge sider i uligheden følger at

ε

(n

2

)= n · ε ·

(n

2− 1

2

)>

(ε

2+ 3

(ε6

)(r+1)t)n2

2.

For n ≥ N ′ gælder saledes for antallet af kanter i G′′:

e(G′′) > e(G)−(ε

2+ 3

(ε6

)(r+1)t)n2

2

≥ (1− 1r

+ ε)(n

2

)−(ε

2+ 3

(ε6

)(r+1)t)n2

2

> (1− 1r

)n2

2

≥ (1− 1r

)(n′)2

2.

Lad nu R være den reducerede graf af G′′. Der er en knude i R for hver klasse i G (knuden visvarer til klassen Ci), og to knuder er forbundet i R netop nar de tilsvarende klasser i G′′ udgøret ikke-tomt γ-regulært par (dvs. med densitet større end d). Lad desuden S være grafen derfremkommer af G′′ hvis alle ikke-tomme klassepar fuldstændiggøres, dvs. at S = R(m). Antallet afkanter mellem to knuder vi,vj i R betegner vi med eR(vi, vj) – dette antal er altid 0 eller 1. Ud frakantantallet i G′′, kan vi sige følgende om antallet af kanter i R:

1k2e(R) =

1k2

∑1≤i<j≤k

eR(vi, vj) =1k2

∑1≤i<j≤k

dS(Ci, Cj)

≥ 1k2

∑1≤i<j≤k

dG′′(Ci, Cj) =1k2

∑1≤i<j≤k

eG′′(Ci, Cj)m2

=1

(km)2e(G′′) =

1(n′)2

e(G′′)

> 12(1− 1

r).

39

Antallet af kanter i R er saledes e(R) > (1 − 1/r)k2/2 ≥ tr(k) (jf. lemma 2.7), sa R indeholderifølge Turans sætning Kr+1 som en delgraf.

Nar Kr+1 er en delgraf af R, er Kr+1(t) en delgraf af R(t). Enhver knude v i Kr+1(t) er forbundettil de rt knuder der ikke ligger i samme klasse i Kr+1(t) som v. Den maksimale knudevalens ∆ iKr+1(t) er dermed ∆ = rt.

Vi vil benytte nøglelemmaet til at vise at Kr+1(t) ogsa er en delgraf af G′′. Vi sætter derforδ = d− γ = ε/2− (ε/6)(r+1)t og

γ0 =δ∆

2 + ∆=

(ε/2− (ε/6)(r+1)t

)rt2 + rt

.

For alle t′ ≤ t gælder Kr+1(t′) ⊆ Kr+1(t), sa alle grafer der indeholder Kr+1(t) indeholderogsa Kr+1(t′). Hvis vi kan vise sætningen for et stort t, vil vi altsa for alle mindre t′ ≤ t have atsætningen er opfyldt nar vi blot sætter N(r, ε, t′) = N(r, ε, t).

Idet der gælderlimt→∞

(2 + rt)1/rt = 1,

findes et t0 ∈ N sadan at der for alle t ≥ t0 gælder (2 + rt)1/rt ≤ 2. Som bemærket ovenfor kan vitillade os i det følgende at antage t ≥ t0, hvorved vi far(ε

6

)(r+1)/r· (2 + rt)1/rt +

(ε6

)(r+1)t≤ ε

6· 2 +

ε

6=ε

2.

Da gælder (ε6

) r+1r·rt· (2 + rt) ≤

(ε

2−(ε

6

)(r+1)t)rt

.

En af forudsætningerne i nøglelemmaet er da opfyldt idet vi har

γ =(ε

6

)(r+1)t≤(ε/2− (ε/6)(r+1)t

)rt2 + rt

= γ0.

Vælg N ′′ ∈ N sa N ′′ · (1− γ)/M(γ) ≥ (t− 1)/γ0. Dermed gælder for alle n ≥ N ′′ at

m ≥ 1− γM(γ)

· n ≥ t− 1γ0

,

hvilket giver t− 1 ≤ γ0m. Alle forudsætninger i nøglelemmaet er saledes opfyldt.Sæt N(r, ε, t) = max(N ′, N ′′). For alle t ≥ t0 og n ≥ N(r, ε, t), opfylder G′′, R og Kr+1(t)

forudsætningerne i nøglelemmaet, og følgelig er Kr+1(t) en delgraf af G′′. Heraf far vi sa endelig atKr+1(t) er en delgraf af G.

40

7 Notationsoversigt

d(v), dG(v) Valensen af knuden v i grafen G (antallet af kanter med v som den eneendeknude).

d(U, V ), dG(U, V ) Densiteten af parret (U, V ) af disjunkte mængder af knuder i G.δ(G) Den minimale knudevalens i G.∆(G) Den maksimale knudevalens i G.E(G) Mængden af kanter i grafen G.e(G) Antallet af kanter i grafen G, dvs. e(G) = |E(G)|.e(U, V ), eG(U, V ) Antallet af U–V -kanter i G. U og V er disjunkte mængder af knuder.e(u, V ) Antallet af kanter pa formen u, v, v ∈ V .EX(n;F ) Mængden af ekstremale grafer med n knuder uden grafen F som delgraf.EX(n;F) Mængden af ekstremale grafer med n knuder uden nogen graf F ∈ F som

delgraf.ex(n;F ) e(G) for en graf G ∈ EX(n;F ).ex(n;F) e(G) for en graf G ∈ EX(n;F).G = (V,E) Graf med knudemængde V og kantmængde E.|G| Antallet af knuder i grafen G, dvs. |G| = |V (G)|.G Den komplementære graf til grafen G.G[U ] Delgrafen af G udspændt af U . Hvis G = (V,E) er G[U ] for U ⊆ V delgrafen

af G med knudemængde U og kantmængde xy ∈ E | x, y ∈ U, dvs. G[U ] =G− (V \ U).

G(t) Lad G = (V,E). G(t) for t ∈ N fas ved at erstatte hver knude x i G med enmængde af t knuder Wx, og forbinde alle knuder i Wx med alle knuder i Wy

hvis xy ∈ E.G− U LadG = (V,E) være en graf og U ⊆ V . Da erG−U grafen med knudemængde

V \ U og kantmængde xy ∈ E | x, y ∈ V \ U, dvs. G− U = G[V \ U ].G−H Lad G = (V,E) være en graf og H være en delgraf af G. Da er G−H grafen

G− V (H).G− v Grafen G− v hvor v ∈ V (G).G+ vw Grafen med knudemængde V (G) og kantmængde E(G) ∪ vw, hvor v, w ∈

V (G).G− vw Grafen med knudemængde V (G) og kantmængde E(G) \ vw.Γ(v) Mængden af naboknuder til knuden v.Kr Den komplette graf med r knuder.n% r Den principale rest af n ved division med r.O(f(n)) Mængden af funktioner g(n) som for et vist N ∈ N og c ∈ R opfylder g(n) ≤

cf(n) for n ≥ N . Hvis g(n) ∈ O(f(n)) skrives g(n) = O(f(n)).o(f(n)) Mængden af funktioner g(n) som opfylder g(n)

f(n) → 0 for n→∞. Hvis g(n) ∈o(f(n)) skrives g(n) = o(f(n)).

Ω(f(n)) Mængden af funktioner g(n) som opfylder f(n) = O(g(n)). Hvis g(n) ∈Ω(f(n)) skrives g(n) = Ω(f(n)).

Tr(n) Den r-partite Turan-graf med n knuder.tr(n) e(Tr(n)).V (G) Mængden af knuder i grafen G.X–Y -kant En kant xy hvor x ∈ X og y ∈ Y .

41

Litteratur

[BB] Bela Bollobas: Modern Graph Theory, s. 103-144. Springer, USA, 2002.

[FH] Frank Harary: Graph theory. Addison-Wesley, USA, 1972.

[KC] V. Kann & P. Crescenzi: A compendium of NP optimization problems.

http://www.nada.kth.se/∼viggo/wwwcompendium/node15.html

Kungliga Tekniska hogskolan, Stockholm.

[KS] J. Komlos & M. Simonovits: Szemeredi’s Regularity Lemma and its Applications in GraphTheory, s. 295-311 i Combinatorics, Paul Erdos is Eighty, bind 2. Janos Bolyai MathematicalSociety, Budapest, Ungarn, 1996.

[MN] J. Matousek & J. Nesetril: Invitation to Discrete Mathematics. Oxford University Press,Storbritannien, 1998.

[PE] P. Erdos: On Sets of Distances of n Points in Euclidean Space, s. 165-169 i PublicationsMathematical Institute of Hungarian Academy of Sciences nr. 5, 1960.

42

Date post:	10-Oct-2020
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Bachelorprojekt for BSc-graden i...

Documents