Colo ings o Randomly Augmen ed G aphs and a
Make -S a egy o he k-Edge-Connec i i y Game
Disse a ion
zu E langung des Dok o g ades de
Ma hema isch-Na u wissenscha lichen Fakul ä
de Ch is ian-Alb ech s-Uni e si ä zu Kiel
o geleg on
Jan E ha d Gees
Kiel, 2024
un e de Be euung on
P o . D . Anand S i as a
E s e Gu ach e : P o . D . Anand S i as a
Zwei e Gu ach e : P o . D . Sö en Ch is ensen
Da um de mündlichen P ü ung : 03. Sep embe 2024
Danksagungen
An diese S elle möch e ich einigen Pe sonen danken, ohne die ich diese A bei nich
in diese Fo m hä e e igs ellen können.
An e s e S elle bedanke ich mich bei P o . D . S i as a ü die Be euung und
Be a ung wäh end meine Fo schungsa bei .
Wei e hin bedanke ich mich bei allen Mi gliede n de A bei sg uppe Disk e e Op-
imie ung de Ch is ian-Alb ech s-Uni e si ä zu Kiel, de en hil eiche Anme kun-
gen mi seh gehol en haben und die mi in unse en Gesp ächen in den Obe sem-
ina en e möglich en, gu e Ideen zu inden und schlech e Ideen als solche zu e kennen
und zu e we en.
Da übe hinaus bedanke ich mich bei meinen El e n und meine Familie, de en
emo ionale und inanzielle Un e s ü zung es mi e möglich ha , s e s mi ollem
Einsa z zu o schen.
Gillian K üge danke ich ü ih e une müdlichen E mu igungen und ih s e s
o enes Oh .
2
Con en s
1 In oduc ion 7
1.1 On he model o Randomly Augmen ed G aphs . . . . . . . . . . . . 7
1.2 On he Ch oma ic Numbe o Random G aphs . . . . . . . . . . . . . 8
1.3 On he Choice Numbe o Random G aphs . . . . . . . . . . . . . . . 9
1.4 On Make -B eake Games . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Ma e ial and Me hods 11
2.1 On he Ch oma ic Numbe o Random G aphs . . . . . . . . . . . . . 11
2.2 On he Choice Numbe o Random G aphs . . . . . . . . . . . . . . . 22
2.3 Winning he k-edge-Connec i i y Game using K i ele ich’s echniques 23
3 On he Ch oma ic Numbe o Randomly Augmen ed G aphs 28
3.1 In oduc ion................................ 28
3.1.1 P e iouswo k........................... 28
3.1.2 Ou esul s ............................ 29
3.2 Bounding he ch oma ic numbe o pe H,p ............... 30
3.2.1 The Case p∈(0,1) iscons an .................. 30
3.2.2 The Case p(n) = n−θ o some θ∈0,1
3............ 33
3.3 Tigh ness o uppe bounds o ce ain g aphs . . . . . . . . . . . . . . 36
3.4 Colo ing Augmen ed G aphs wi h Hos G aphs o small Ch oma ic
Numbe .................................. 37
3.5 Conclusion................................. 42
4 On he Choice Numbe o Randomly Augmen ed G aphs 44
4.1 In oduc ion................................ 44
4.1.1 P e iousResul s ......................... 44
4.1.2 Ou Resul ............................ 45
4.2 Bounding he Choice Numbe o Randomly Augmen ed G aphs . . . 45
4.3 Rema kson igh ness........................... 49
4.4 Conclusion................................. 50
5 An Algo i hm o win he biased k-Edge-Connec i i y and k-Fac o
Games as 51
5.1 In oduc ion................................ 51
5.1.1 P e iouswo k........................... 51
5.1.2 Ou esul s ............................ 52
5.1.3 Me hods and Inno a ions . . . . . . . . . . . . . . . . . . . . . 53
3
CONTENTS
5.2 Desc ibing he Algo i hm Hamil on-Cycles ............... 53
5.2.1 S age 1: C ea ing a G aph consis ing o an Expande and ew
pa hs................................ 54
5.2.2 S age 2: Closing kHamil on Cycles . . . . . . . . . . . . . . . 55
5.3 Bounding he Numbe o Rounds played . . . . . . . . . . . . . . . . 57
5.4 Ve i ying Make ’s S a egy . . . . . . . . . . . . . . . . . . . . . . . . 62
5.5 Desc ibing he algo i hm used o p o e k-Edge Connec i i y . . . . . 77
5.5.1 S age 3: Bonus S age o odd k................. 78
5.6 Analyzing he du a ion o S age 3 . . . . . . . . . . . . . . . . . . . . 79
5.7 P o ing he k-Edge-Connec i i y o Make ’s G aph . . . . . . . . . . 83
5.8 Conclusion and Open Ques ions . . . . . . . . . . . . . . . . . . . . . 85
4

Summa y
In his hesis we s udy he beha io o wo g aph p ope ies on andomly augmen ed
g aphs as well as mul iple Make -B eake games. We p o e igh uppe bounds o
he ch oma ic numbe and he choice numbe o andomly augmen ed g aphs and
gi e an uppe bound o he numbe o u ns i akes Make o win se e al Make -
B eake games.
In Chap e 2 we gi e sligh ly imp o ed p obabili y bounds o he alues o he
ch oma ic numbe o and he choice numbe o he Gn,p andom g aph model using
echniques used by Bollobás [Bol88] and Kahn [Alo93] espec i ely, combining hem
wi h a esul by K i ele ich e al. [KS VW03], as his allows o imp o ed esul s
in Chap e 3 and Chap e 4. We also calcula e an explici bound o he numbe
o u ns Make needs o win he biased k-edge-connec i i y game, using well-known
s a egies, as such esul s did no gi e explici uppe bounds o he numbe o u ns
bu a he ocused on iden i ying ce ain games as Make wins.
In Chap e 3 we show ha o andomly augmen ed g aphs pe H,p he ch oma ic
numbe χpe H,p o each ε > 0is bounded om abo e by
χpe H,p≤(1 + ε)nlog(b)
2(log(n)−log(χ(H))) a.a.s. (1)
whe e b= 1/(1−p)as long as p∈(0,1) is cons an and χ(H)∈o (n).We also show
ha inequali y 1 holds, i p=p(n) = n−θ o some θ∈(0,1/3) and χ(H)≤n1−3θ.
Since he p oo is non-cons uc i e we also gi e sligh ly less powe ul cons uc i e
p oo s.
In Chap e 4 we show ha he uppe bound es ablished in Chap e 3 o he
ch oma ic numbe o a andomly augmen ed g aph also holds o he choice numbe
o he andomly augmen ed g aph, i.e. o each ε > 0
χlpe H,p≤(1 + ε)nlog(b)
2(log(n)−log(χ(H))) a.a.s. (2)
whe e b= 1/(1 −p)as long as p∈(0,1) is cons an and χ(H)≤n−θ o some
θ∈(0,1/2).
In Chap e 5 we p o e ha Make can win he biased Make -B eake k-Hamil on-
Cycle game in a mos kn + o (n) ounds. We use his esul o show ha Make
can win he k-edge-connec i i y game in a mos k
2n+ o (n) u ns and ha Make
can win he k- ac o game in a mos lk
2mn+ o (n) o each k∈N≥2.In he case
o he k-edge-connec i i y game his bound on he numbe o u ns is op imal up
o he o (n) e m. The bound in he k- ac o game is op imal o e en k, while o
odd ka lowe bound o k
2ncould be possible. Fo each o hese h ee games he
bound was imp o ed by a ac o o a leas 8. We achie e hese esul s by building
an expande -like s uc u e on a se o θn
√log(n) e ices and amilies o di e en ly
colo ed pa hs which will o m he basis o he Hamil on cycles we build, be o e we
s a closing he Hamil on cycles. This app oach is a gene aliza ion o an app oach
in oduced by B üs le e al. [BCN+23] ha showed ha Make can win he biased
Hamil onici y game in a mos n+ o (n)mo es.
5
Zusammen assung
In diese A bei un e suchen wi das Ve hal en on zwei Eigenscha en zu ällig aug-
men ie e G aphen sowie meh e e Make -B eake Spiele. Wi beweisen scha e
obe e Sch anken ü die ch oma ische Zahl und die lis ench oma ische Zahl zu ällig
augmen ie e G aphen und geben e schiedene obe e Sch anken ü die Anzahl de
Züge, in denen Make gewisse biased Make -B eake Spiele gewinnen kann.
In Kapi el 2 geben wi leich e besse e Wah scheinlichkei ssch anken ü die
We e de ch oma ischen Zahl und de lis ench oma ischen Zahl des Gn,p Zu alls-
g aphen. Hie ü e wenden wi Techniken on Bollobás [Bol88] bzw. Kahn [Alo93]
und kombinie en diese mi einem Resul a on K i ele ich e al. [KS VW03], da
dies eine Ve besse ung unse e E gebnisse in den Kapi eln 3 und 4 e möglich . Des
Wei e en be echnen wi explizi die bes e bishe bekann e obe e Sch anke ü die
Anzahl de Züge, die Make benö ig , um das k-Kan enzusammenhangsspiel zu
gewinnen. Die exis ie enden E gebnisse ließen diese In o ma ion o aus.
In Kapi el 3 zeigen wi , dass die ch oma ische Zahl on zu ällig augmen ie en
G aphen χpe H,p ü jedes ε > 0nach oben du ch
χpe H,p≤(1 + ε)nlog(b)
2(log(n)−log(χ(H))) a.a.s. (3)
besch änk is , wobei b= 1/(1 −p),solange p∈(0,1) kons an und χ(H)∈o (n)
is . Wi zeigen auße dem, dass Ungleichung 3 auch gil , wenn p=p(n) = n−θ ü
ein θ∈(0,1/3) und χ(H)≤n1−3θgil . Da diese Beweis nich kons uk i is ,
geben wi ein schwäche es kons uk i es Resul a an.
In Kapi el 4 zeigen wi , dass die obe e Sch anke ü χpe H,paus Kapi el 3
auch ü die lis ench oma ische Zahl on zu ällig augmen ie en G aphen gil . So
gil ü alle ε > 0
χlpe H,p≤(1 + ε)nlog(b)
2(log(n)−log(χ(H))) a.a.s. (4)
wobei b= 1/(1 −p),solange p∈(0,1) kons an und χ(H)≤n−θ ü ein θ∈(0,1)
is .
In Kapi el 5 beweisen wi , dass Make ü jedes k≥2das biased Make -B eake
k-Hamil onk eisspiel in höchs ens kn + o (n)Zügen gewinnen kann. Wi e wenden
dieses Resul a , um zu zeigen, dass Make das k-Kan enzusammenhangspiel in höch-
s ens k
2n+o (n)Zügen gewinnen kann und dass Make das k-Fak o spiel in höchs ens
lk
2mn+ o (n)Zügen gewinnen kann. In dem Fall des k-Kan enzusammenhangspiels
s ell dies bis au den o (n)Te m die op imale obe e Sch anke da . Die Sch anke
im k-Fak o spiel is ü ge ade kscha , wäh end ü unge ade kun e Ums än-
den eine un e e Sch anke on k
2nmöglich wä e. In jedem diese Spiele wu de die
obe e Sch anke um einen Fak o g öße als 8 gesenk . Wi beweisen diese Resul a e,
indem wi eine expande ähnliche S uk u au θn
√log(n)Kno en und e schieden-
a bige P ade, die die G undlage de Hamil onk eise bilden, kons uie en. Diese
Ansa z e allgemeine ein Resul a on B üs le e al., das besag , dass Make das
Hamil onk eisspiel in höchs ens n+ o (n)Zügen gewinnen kann.
6
Chap e 1
In oduc ion
1.1 On he model o Randomly Augmen ed G aphs
The mos amous andom g aph model is he Gn,p model. Le p:N→(0,1) and
le n∈N.We say ha G= (V, E)is a Gn,p-g aph (G∼ Gn,p) i |V|=nand each
po en ial edge e∈V
2is chosen independen ly wi h p obabili y p(n).In his hesis
we will concen a e on wo main cases.
1. pis cons an o
2. pis some mono onously dec easing unc ion, o en in he shape p(n) = n−γ
o some γ > 0.
We u he assume ha V= [n].The Gn,p model was i s in oduced by Gilbe
[Gil59] in 1959 and is highly ela ed o he Gn,M andom g aph model in oduced by
E dős and Rényi [ER59] whe e a andom subse o size M≤nis chosen. Bo h o
hese models ha e been s udied ex ensi ely. Fo a deepe analysis o he Gn,p model
we e e he eade o he books o Bollobás [Bol85] and F ieze and Ka oński [FK16].
In Chap e 3 and Chap e 4 o his hesis we s udy a gene aliza ion o he Gn,p
andom g aph model. Conside a de e minis ic g aph H= ([n], EH)and p:N→
(0,1) an a bi a y unc ion. We de ine he andomly augmen ed g aph pe H,p :=
H∪Gn,p as he union o he so-called hos -g aph Hand a andom Gn,p-g aph. No e
ha i His he emp y g aph, his model yields he andom g aph Gn,p.
In hei ounda ional pape [BFM03] Bohman e al. in oduced a hyb id g aph
model, whe e he hos -g aph has a leas linea (in n) minimum deg ee and he
andom g aph is a Gn,M g aph. In he cu en li e a u e bo h o he andom g aph
models desc ibed abo e ha e been s udied as augmen ing g aphs. Howe e , since
in he exis ing li e a u e he e m pe u bed g aph is al eady hea ily connec ed o
he es ic ion on he minimum deg ee, see o example [CHMP20], [BMPP20] o
[BPSS23], and he hos g aphs we a e in e es ed in a e g aphs Hwi h bounded
ch oma ic numbe χ(H),we decided o use he e m augmen ed g aph in his hesis.
7
1.2. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
1.2 On he Ch oma ic Numbe o Random G aphs
Fo a g aph G= (V, E) he ch oma ic numbe χ(G)o Gis he minimum numbe
o colo s needed o colo he e ices o Gsuch ha no wo adjacen e ices a e
o he same colo . Since he numbe o colo s in his chap e is no bounded by
a cons an numbe we will no use eal colo s { ed, blue, . . .}bu use he i s ew
na u al numbe s as colo s. This is s anda d p ocedu e [Bol98]. Tha is, o a k∈N
he unc ion φ:V→[k]is called a k( e ex) colo ing o G. φ is called a p ope
k-colo ing o Gi { , w} ∈ E=⇒φ( )=φ(w).
χ(G) := min {k:∃(φ:V→[k]) : { , w} ∈ E=⇒φ( )=φ(w)}.
No e ha o en imes a p ope e ex k-colo ing φ:V→[k]will be e e ed o as
jus a colo ing o G, i he usage is clea om he con ex . Le φ:V→[k]be a
p ope colo ing o G hen, o each j∈[k]φ−1(j)is called he j-colo class o G
wi h espec o φ. No e ha by de ini ion each colo class is an independen se in
G.
The ch oma ic numbe o he Gn,p model has been o in e es o a long ime. I
was i s s udied by E dős in [ER59] and i s asymp o ic beha io was i s desc ibed
by Bollobás [Bol88] who showed ha o each ε > 0χ(Gn,p)≤(1 + ε)nlog(b)
2 log(n),i pis
cons an , o p=p(n)≥n−θ, o some θ∈(0,1/3) and b= 1/(1 −p).
In his hesis we gi e a gene aliza ion o he esul o Bollobás by showing ha
o each ε > 0
χpe H,p≤(1 + ε)nlog(b)
2 (log(n)−log(χ(H)))
as long as pis cons an . I p=p(n) = n−θ, o some θ∈(0,1/3),we can show he
same uppe bound as long as χ(H)≤n1−3θ.I is easy o see ha his indeed is a
gene aliza ion o he amous Bollobás esul by plugging in he emp y g aph which
has ch oma ic numbe 1.
We achie e his esul by conside ing an op imal colo ing o Hand di iding i s
colo classes in o la ge colo classes which ha e a leas sligh ly below a e age size
and small colo classes which a e e en smalle . Building upon his we calcula e he
expec ed alue o he ch oma ic numbe s o he g aphs induced by hese colo classes
and inally apply McDia mid’s bounded di e ences inequali y [McD89].
We also show ha o ce ain hos g aphs, o example he comple e χ(H)-pa i e
g aph, his uppe bound is igh .
Fu he mo e, since he app oach desc ibed abo e is non-cons uc i e, we s udy
an algo i hm ha colo s he andomly augmen ed g aph pe H,p by colo ing he
(pu ely andom) g aphs induced by he colo classes o an op imal colo ing o H.
This yields he same uppe bound as ou non-cons uc i e app oach, bu ails o
hos g aphs o ch oma ic numbe a leas n/ log(n)1/2.
8
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
≤exp −cn2p7
log(n)8!.
We conside he ollowing implica ion o Theo em 2.5.
Co olla y 2.6 Le p∈(0,1) be cons an . Fo any ε > 0and su icien ly la ge
n=n(ε)∈Nwe ha e
E(χ(Gn,p)) ≤(1 + ε)nlog(b)
2 log(n).
P oo o Co olla y 2.6. Le ε > 0and k= (1 + ε
2)nlog(b)
2 log(n).
E(χ(Gn,p)) =
n
X
i=1
i·P(χ(Gn,p) = i)
≤
k
X
i=1
i·P(χ(Gn,p) = i)+(n−k)P(χ(Gn,p)> k)
≤k
k
X
i=1
P(χ(Gn,p) = i) + nexp −cn2p7
log(n)8!
≤1 + ε
2nlog(b)
2 log(np)+nexp −cn2p7
log(n)8!
(By Theo em 2.5 wi h ε′=ε/2)
≤1 + ε
2nlog(b)
2 log(np)+ε·nlog(b)
2·2 log(n)(2.4)
= (1 + ε)nlog(b)
2 log(n).
The inequali y in (2.4) holds, since p(n)> n−1
7and hus
nexp −cn2p7
log(n)8!≤nexp −cn
log(n)8!≤ε·nlog(b)
2·2 log(n)
As seen in he p oo o Theo em 2.5, i pis cons an , in he inal s ep o Algo-
i hm 2.1.1 i is possible o colo he emaining e ices wi h a new colo o each
such e ex. This s a egy is no success ul in calcula ing a igh bound in case o
p=p(n)∼n−θ. He e he numbe o emaining e ices is oo la ge o be handled
in such a way. To be able o analyze colo ings o Gn,p o p=p(n)∼n−θwhe e
θ∈0,1
3we need a colo ing algo i hm o he small colo classes. As Bollobás in
[Bol88] we use he well-known g eedy colo algo i hm.
15

2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
Algo i hm 2.1.2: G eedy Colo
Inpu : A andom g aph Gn,p
Ou pu : A colo ing o he e ices o Gn,p
1while The e is a se o uncolo ed e ices do
2Choose a maximally independen se Io uncolo ed e ices;
3Colo Iwi h a new colo ;
4end
We also gi e he ollowing mino imp o emen o he esul o he g eedy colo
algo i hm.
Theo em 2.7 Le n−τ≤p≤n−θ o some a bi a y, bu ixed τ, θ ∈0,1
3. Fu he
le χg(Gn,p)be he numbe o colo s used by G eedy Colo . Then
P χg(Gn,p)≥(1 + ε)nlog(b)
log(np)!≤exp −(1 + o(1))n3.
P oo o Theo em 2.7. We will ollow he pa e n o he p oo in [FK16, Theo em
7.9] gi en o cons an pwi h sligh modi ica ions. Suppose ha in some i e a ion
o Algo i hm 2.1.2 he e a e a leas n0=np
(logb(n))2 e ices uncolo ed. Le Ube he
se o uncolo ed e ices. Le κ=4
θand k1= logb(np)−κlogb(logb(n)). Wi h he
i ial es ima e k1≤logb(np)≤logb(np)we ge
log(k1) + k1log(n)+2k1−logb(n)κ−2
≤log(logb(np)) + logb(np) log(n) + 2 logb(np)−logb(n)κ−2
≤logb(n)(log(n)+2−o(1)) −logb(n)κ−2
=−logb(n)(logb(n)κ−3−log(n)−2 + o(1))
=−logb(n)(log(n)κ−3log(b)−κ+3 −log(n)−2 + o(1))
=−logb(n)(log(n)κ−3(1 ±o(1))−κ+3p−κ+3 −log(n)−2 + o(1))
(using log(b) = (1 ±o (1))p)
=−logb(n)(log(n)κ−3(1 ±o(1))p−κ+3 −log(n)−2 + o(1))
(using ha κis cons an and hus (1 ±o(1))−κ+3 = (1 ±o (1)))
=−(1 ±o(1)) logb(n)(log(n)κ−3p−κ+3 −log(n)−2 + o(1))
=−(1 ±o(1)) logb(n)p−κ+3(log(n)κ−3−(log(n) + 2 + o(1))pκ−3)
≤−(1 ±o(1)) logb(n) log(b)−κ+3 ·(log(n)κ−3−(log(n) + 2)n−τ(κ−3)
| {z }
=o(1)
)
(again wi h log(b) = (1 ±o (1))pand p≥n−τ)
=−(1 ±o(1)) logb(n) log(b)−κ+3 ·log(n)κ−3(1 −o (1))
≤−(1 ±o(1)) logb(n)κ−2.
Now le Ube a se o ca dinali y n0, hen
P(∃S:|S| ≤ k1, S is a maximally independen se in U)
≤X
S⊆U;|S|≤k1
P(Sis a maximally independen se in U)
16
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
=
k1
X
=1 X
S⊆U;|S|=
P(Sis a maximally independen se in U)
=
k1
X
=1 X
S⊆U;|S|=
P(Sis an independen se in U)
·P( o each u∈(U S) he e exis s s∈S:{u, s} ∈ E(Gn0,p))
=
k1
X
=1 X
S⊆U;|S|=
P(Sis an independen se in U)
·Y
u∈U S
P( he e exis s s∈S:{u, s} ∈ E(Gn0,p))
=
k1
X
=1 X
S⊆U;|S|=
P(Sis an independen se in U)
·Y
u∈U S
(1 −P( o all s∈S:{u, s}/∈E(Gn0,p)))
=
k1
X
=1 X
S⊆U;|S|=
P(Sis an independen se in U)
·Y
u∈U S1−(1 −p) 
=
k1
X
=1 X
S⊆U;|S|=
(1 −p)(
2)1−(1 −p) n0−
(since |U S|=n0− )
=
k1
X
=1 n
!(1 −p)(
2)1−(1 −p) n0−
≤
k1
X
=1 ne
(1 −p) −1
2
exp −(n0− )(1 −p) (since 1−x≤e−x o all x)
=
k1
X
=1
(1 −p)(
2)
| {z }
≤1
n exp ( ) exp  (1 −p) exp −n0(1 −p) 
≤
k1
X
=1
n exp  + (1 −p) exp −n0(1 −p) 
=
k1
X
=1 nexp(1 + (1 −p) ) exp(−n0(1 −p
|{z}
=b−1
) )
≤k1

nexp(1 + (1 −p)k1
| {z }
≤2
)


k1
exp −n0b−k1(since b > 1)
=k1(ne2)k1exp −np
logb(n)2exp (−log(b)(logb(np)−κlogb(logb(n))))!
17
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
=k1(ne2)k1exp −np
logb(n)2exp −log(b)(log(np)−κlog(logb(n)))
log(b)!!
=k1(ne2)k1exp −np
logb(n)2exp (−(log(np) + κlog(logb(n))))!
=k1(ne2)k1exp −np
logb(n)2
logb(n)κ
np !
=k1(ne2)k1exp −logb(n)κ−2
= exp 


log(k1) + k1log(n)+2k1
| {z }
o(logb(n)κ−2)
−logb(n)κ−2



= exp −(1 −o(1)) logb(n)κ−2(as shown abo e)
≤exp −(1 ±o(1)) log(n)κ−2p−(κ−2)(wi h log(b) = (1 ±o (1)) p)
≤exp −(1 ±o(1))nθ(κ−2) since p≤n−θand log(n)κ−2≥1
= exp −(1 ±o(1))nθ(4
θ−2) as κ=4
θ
= exp −(1 ±o(1))n4−2θ
≤exp −(1 ±o(1))n3.since θ≤1
3
Thus he p obabili y ha in e e y se o a leas n0 e ices e e y maximally
independen se is o size a leas k1is a leas 1−exp (−cn3).So in each s ep
be o e he numbe o uncolo ed e ices d ops below n0, a leas k1 e ices a e
colo ed. The e o e, he p obabili y ha mo e han (1 +ε)n
logb(n)≥n
k1+n0colo s a e
used is a mos exp (−(1 + o(1))n3).
We now conside colo ings o Gn,p using an asymp o ically op imal amoun o
colo s o he case p(n)≤n−θ. The ollowing algo i hm can be used o ob ain a
colo ing which is an 1+εapp oxima ion o an op imal colo ing wi h a sligh ly be e
p obabili y bound o p(n)∼n−θas in [Bol88]. This will be used la e .
Fu he mo e we use he ollowing algo i hm o Bollobás [Bol88].
Algo i hm 2.1.3:
Inpu : A andom g aph Gn,p
Ou pu : A colo ing o he e ices o Gn,p
1while A leas n
log(np) e ices emain uncolo ed and i he e is an uncolo ed
independen se Io size 2 logb(np)−4 logb(logb(np)) do
2Colo Iwi h a new colo ;
3end
4colo he emaining g aph using Algo i hm 2.1.2;
Lemma 2.8 Le n−τ≤p≤n−θ o some a bi a y, bu ixed τ, θ ∈0,1
3. Then
he p obabili y ha he e exis s a e ex se V1⊆Vo size ν(n) = n
log(np)such ha
V1does no con ain an independen se o size k0(ν)∼2 logb(np)∼2 logb(np)−
18
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
4 logb(log(np)) is bounded om abo e by
P(∃S⊆[n] : |S|=ν∧α(Gn,p[S]) < k0(ν)) ≤exp − c2n2p3
log(n)6!!.
P oo . Le ν=n
log(np).We ha e k0(ν)∼2 logb(np)∼2 logb(np)−4 logb(log(np)).
Now,
P(∃S⊆[n] : |S|=ν∧α(Gn,p[S]) < k0(ν))
≤ n
ν!exp −c1ν2p3
log(ν)4!(by Theo em 2.3 o some cons an c1>0)
≤exp −νc1νp3
log(ν)4+νlog(n)!
= exp −n
log(np)
c1np3
log(np)(log(n)−log(log(np)))4+n
log(np)log(n)!
≤exp − c2n2p3
log(n)6!!,(a.3)
and he las inequali y holds o a cons an c2>0and su icien ly la ge n, because
log(np)≤log(nn−θ)≤(1 −θ) log(n).
We also gi e he ollowing mino imp o emen o a esul o Bollobás using
Algo i hm 2.1.3 and Lemma 2.8.
Theo em 2.9 Le θ∈0,1
3,δ > 0and n−1
3+δ≤p(n)≤n−θ. Fo su icien ly la ge
n∈N he e is a cons an c > 0such ha
P χ(Gn,p)≥(1 + ε)np
2 log(np)!≤exp − cn2p3
log(n)6!!.
Fu he mo e he p obabili y ha Algo i hm 2.1.3 ails o cons uc a colo ing wi h a
mos (1 + ε)np
2 log(np)colo s is a mos exp −cn2p3
log(n)6.
P oo o Theo em 2.9. By Lemma 2.8 he p obabili y ha Algo i hm 2.1.3 ails o
ind an independen se o size k1:= 2 logb(np)−logb(logb(np)) as long as a leas
ν=n
log(n) e ices emain is a mos exp −c2n2p3
log(n)6.Hence he numbe o colo s
used in he while-loop o Algo i hm 2.1.3 is a mos n
k1≤(1+ ε
2)nlog(b)
log(np). Fu he mo e,
since he emaining ν e ices induce a Gν,p, he p obabili y ha Algo i hm 2.1.2
uses mo e han
(1 + ε)νlog(b)
log(ν)
=(1 + ε)νlog(b)
log(n)−log log(np)
=(1 + ε)νlog(b)
(1 −o (1)) log(n)
=1 + ε
1−o (1) ·nlog(b)
log(np) log(n)
19
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
≤1 + ε
1−o (1) ·nlog(b)
log(np)2
=ε
2
nlog(b)
log(np)·2
ε
1 + ε
(1 −o(1)) log(np)
| {z }
<1 o su icien ly la ge n
≤ε
2
nlog(b)
log(np)
colo s o colo he emaining ν e ices can be es ima ed by Theo em 2.7 o be a
mos
exp −(1 + o(1))ν3= exp −(1 + o(1))n3
log(np)3!≤exp − (1 + o(1))n3
log(n)3!!.(a.4)
Thus he p obabili y ha Algo i hm 2.1.3 uses mo e han (1 + ε)nlog(b)
2 log(np)colo s
is a mos
P Algo i hm 2.1.3 uses mo e han(1 + ε)nlog(b)
2 log(np)colo s!
≤P(The while-loop o Algo i hm 2.1.3 colo s less han ν e ices)
+P Algo i hm 2.1.2 uses mo e han ε
2
nlog(b)
log(np)colo s!
≤exp − c2n2p3
log(n)6!!+ exp − (1 + o(1))n3
log(n)3!!
(using Lemma 2.8 and a.4)
≤exp − c3n2p3
log(n)6!!,
o some cons an c3>0.The las inequali y holds due o he ac ha
exp −(1+o(1))n3
log(n)3∈oexp −c2n2p3
log(n)6.
Now we a e able o gi e an uppe bound o he expec ed alue o χ(Gn,p).
Co olla y 2.10 Le θ∈0,1
3,δ > 0and n−1
3+δ≤p(n)≤n−θ. Le ε > 0. Fo
su icien ly la ge n∈Nwe ha e
E(χ(Gn,p)) ≤(1 + ε)np
2 log(np).
P oo . Le ε > 0and k= (1 + ε
2)np
2 log(np). Le u he nbe su icien ly la ge. Then,
E(χ(Gn,p)) =
n
X
i=1
i·P(χ(Gn,p) = i)
=
k
X
i=1
i·P(χ(Gn,p) = i)
n
X
i=k+1
i·P(χ(Gn,p) = i)
20

2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS
≤
k
X
i=1
i·P(χ(Gn,p) = i) + nP(χ(Gn,p)> k)
≤(1 + ε
2)np
2 log(np)+nexp − cn2p3
log(n)5!!
(by Theo em 2.9 wi h ε′:= ε/2)
= (1 + ε)np
2 log(np).
Fo he las inequali y we use
nexp − cn2p3
log(n)5!!≤np
2 log(np).
This holds o su icien ly la ge n, because
lim
n→∞nexp − cn2p3
log(n)5!!= 0 and lim
n→∞
np
2 log(np)=∞.
In addi ion o hese esul s ha es ablish bounds on p obabili ies, we equi e
he ollowing basic esul o he ch oma ic numbe o he union o any wo g aphs
o analyze he ch oma ic numbe o pe H,p g aphs.
Lemma 2.11 (Di ide and Colo ) Le G:= (V, EG)and H:= (V, EH)be g aphs.
Fu he le C ⊆ P(V)be a pa i ion o Vsuch ha e e y S∈ C is an independen
se in G. Then
χ(G∪H)≤X
S∈C
χ(H[S]) .
I Gis a comple e k-pa i e g aph and Cis a k-pa i ion o he e ices o Gas
abo e, hen
χ(G∪H) = X
S∈C
χ(H[S]) .
The p oo is kind o olklo e. Fo eade s’ con enience we s a e i he e b ie ly.
P oo . Fo each S∈ C colo he g aph wi h χ(H[S]) colo s ha a e no ye used.
This is a p ope colo ing o G∪Hsince no edges in Gexis be ween e ices o he
same colo , as Cis a se o independen se s. Fu he mo e, by cons uc ion he e
a e no edges in Hbe ween e ices o he same colo , since no colo is used o
e ices con ained in di e en membe s o C. This p o es he inequali y. Le Gbe
a comple e k-pa i e g aph and Cis a k-pa i ion o he e ices o Vas abo e, he
colo ing is e en op imal, since he H[S]a e al eady op imally colo ed and o each
pai o membe s o C, e e y edge be ween hem al eady exis s. Thus, e e y o he
p ope colo ing o he g aph uses a leas as many colo s as he colo ing cons uc ed
he e.
21
2.2. ON THE CHOICE NUMBER OF RANDOM GRAPHS
Fu he mo e, we equi e he ollowing a ia ion o he union bound which is a
basic esul o s ochas ic.
Lemma 2.12 Le (Ω,Σ,P)be a p obabili y space and k∈N.Fo each i∈[k]le Xi
be a andom a iable and Aiin R.Then
P k
X
i=1
Xi≤
k
X
i=1
Ai!≤
k
X
i=1
P(Xi≤Ai).
P oo . Le ˜
Ω := nω∈Ω : Pk
i=1 Xi(ω)>Pk
i=1 Aioand o each i∈[k]le Ωi:=
{ω∈Ω : Xi(ω)> Ai}.I o some ω∈Ω he e is Xi(ω)> Ai o all i∈[k], hen
Pk
i=1 Xi>Pk
i=1 Ai.So, ˜
Ω⊇Ti∈[k]Ωiand ˜
Ωc⊆(Ti∈[k]Ωi)c=Si∈[k]Ωc
i.This implies
P k
X
i=1
Xi≤
k
X
i=1
Ai!=P˜
Ωc≤P
[
i∈[k]
Ωc
i
≤
k
X
i=1
P(Ωc
i) =
k
X
i=1
P(Xi≤Ai).
2.2 On he Choice Numbe o Random G aphs
The p oo ha he ollowing esul holds was i s published by Alon [Alo93], who
a ibu es i o p i a e communica ion om Kahn.
Lemma 2.13 (Kahn, Alon) Le G= (V, E)be a g aph and b > 1be a cons an ,
such ha e e y se o a leas n
log(n)2 e ices con ains an independen se o size a
leas (1 −ε)2 logbn. Then χl(G)≤(1 + ε)n
2 logb(n).
They hen combined his esul wi h he p obabili y esul o Bollobás. We will
gi e he sigh ly s onge esul elying on Lemma 2.4. This implies
Theo em 2.14 (Va ia ion o Kahn and Alon) Le 0<p<1be cons an and ε > 0,
hen he e exis s n(ε)∈Nsuch ha o all n≥n(ε)
P χl(Gn,p)>(1 + ε)n
2 logb(n)!≤exp cn2
log(n)8!.
P oo . By Lemma 2.4 e e y se o a leas n/ log(n)2 e ices con ains an indepen-
den se o size a leas (1−ε)2 logb(n).Wi h p obabili y a leas 1−exp (cn2/log(n)8).
Thus by Lemma 2.13 he p obabili y ha he choice numbe o GH,p exceeds (1 +
ε)n
2 logb(n)is a mos
P χl(Gn,p)>(1 + ε)n
2 logb(n)!≤exp cn2
log(n)8!.
22
2.3. WINNING THE k-EDGE-CONNECTIVITY GAME USING
KRIVELEVICH’S TECHNIQUES
2.3 Winning he k-edge-Connec i i y Game using
K i ele ich’s echniques
In his sec ion we will p o e he ollowing esul ha is men ioned bu no p o en
by K i ele ich [K i10]. I is le as an exe cise in [HKSS14, Exce cise 6.7.2]. I is
he cu en ly bes -known es ima e o he numbe o ounds Make needs o win
he (1 : b)Make -B eake game o kedge-disjoin Hamil on cycles i b≤(1 −ε)n.
Since I could no loca e a p oo , I will gi e one he e.
Theo em 2.15 (Rema k o K i ele ich) Le ε > 0and k∈N.The e exis s n0∈N
such ha o e e y n∈N≥n0Make has a s a egy o cons uc kedge disjoin
Hamil on cycles in he (1 : b)game played on he comple e g aph on n e ices in a
mos min(13n, (9k+ 3)n) + o (n) ounds o e e y b≤(1 −ε)n.
In each s ep Make will use he ollowing algo i hm o cons uc a g aph o
minimum deg ee min(8k+ 3,12) =: κin κn u ns wi h posi i e p obabili y. No e
ha he minimum can be a oided i k≥2which is he case we a e mos in e es ed
in. This algo i hm is due o Gebaue and Szabo [GS09].
Algo i hm 2.3.1: Algo i hms o minimum deg ee game
Inpu : A se B⊆Eclaimed by B eake and a se M⊆Eclaimed by
Make
Ou pu : An edge e∈E (B∪M)
1Choose a e ex ∈Vwi h degM( )< κ ha maximizes
dang := degB( )−2bdegM( );
2Choose a e ex w∈V { }such ha { , w}/∈(B∪M)is unclaimed
uni o mly a andom.
To p o e Theo em 2.15 he ollowing Lemma will be used. I is i s s a ed by
K i ele ich [K i10] bu was p o ed wi h echniques o Gebaue and Szabo [GS09].
I analyzes Algo i hm 2.3.1.
Lemma 2.16 (K i ele ich) Fo e e y ε > 0 he e exis s a ixed δε>0such ha
by playing acco ding o Algo i hm 2.3.1, o all ∈VMake chooses he κ- h edge
inciden in a a ime when dB( )≤(1 −δε)nin he 1 : (1 −ε)n
log(n)game.
Fu he i can be shown ha Make cons uc ed a (δεn, 2k)-expande wi h posi-
i e p obabili y a e κ ounds by ollowing Algo i hm 2.3.1, whe e δε∈(0,1) is he
same as in Lemma 2.16.
Theo em 2.17 Fo e e y ε > 0Make cons uc s a (δεn, 2k)-expande in a mos
κn ounds by ollowing Algo i hm 2.3.1 in each s ep in he (1 : (1 −ε)n
log(n))game
wi h posi i e p obabili y.
P oo . Suppose ha Make s g aph is no a (δεn, 2k)expande a e Make played
each ound by Algo i hm 2.3.1 un il each e ex had Make deg ee κ. Then he e
exis s a subse K⊆V S o size |A|=i≤δεnsuch ha NM(K)⊆L o some
L⊆V Kwi h |L|= 2si −1.Since he minimum deg ee in is Make ‘s g aph is κ,
we can assume ha i≥5.
23
2.3. WINNING THE k-EDGE-CONNECTIVITY GAME USING
KRIVELEVICH’S TECHNIQUES
Excu sion on i≥5:
Assume ha |K| ≤ 4.Since e e y e ex in Khas a minimum deg ee o κand a
mos 3o i s neighbou s a e in K, we can assume ha each elemen o Khas a leas
κ−3neighbou s in V K. In he wo s case all e ices in Kha e all neighbou s
ou side o Ain common. We see ha |NM(K)| ≥ κ−3.Since Mis supposed o be
a(δεn, 2k)-expande , we need o ensu e ha |NM(K)| ≥ 2k|K|.This holds because
|NM(K)| ≥ κ−3 = (8k+ 3) −3≥8k= 2k|K|.
Fu he mo e he e a e a leas κi
2edges o Make inciden in K. Now one o wo
cases holds.
Case 1: A leas κi
4edges we e chosen om Kand wen in o K∪L.
Case 2: A leas κi
4edges we e chosen om Land wen in o K.
I a some poin du ing he game a choice is made om a e ex ∈K, he
B eake deg ee in is a mos (1 −δε)nand he Make deg ee is a mos κ−1.
The e o e he e we e a leas δεn−κ+ 1 unclaimed edges inciden o . Thus he
p obabili y ha Make chose an edge such ha he second endpoin belongs o K∪L
is a mos
|K∪L|−1
δεn−κ+ 1 =2ki −1 + i−1
δεn−κ+ 1 =(2k+ 1)i−2
δεn−κ+ 1
ega dless o he his o y o he game.
Thus he p obabili y ha Case 1 holds, which is he case i such a choice has been
made a leas κi
4 imes. This is a mos
(2k+ 1)i−2
δεn−κ+ 1 !κi
4
.
Fo a single choice made om ∈L he p obabili y ha he o he endpoin is
in Ais a mos |K|
δεn−κ+1 since as shown abo e a leas δεn−κ+ 1 unclaimed edges
we e inciden in when he edge was chosen. Since a mos κ|L|choices a e made
om L, he p obabili y ha a leas κi
4o hem end up in Kand hus Case 2 holds
is a mos κ|L|
κi
4!i
δεn−κ+ 1κi
4.
Thus he p obabili y ha a leas one o he Cases holds o a speci ic K⊆V
wi h |K|=iis a mos
(2k+ 1)i−2
δεn−κ+ 1 !κi
4
+ κ|L|
κi
4!i
δεn−κ+ 1κi
4
≤ (2k+ 1)i2
δεn!κi
4
+ κ2si
κi
4!i
δεn−κ+ 1κi
4
≤ (2k+ 1)i2
δεn!κi
4
+κ2si4e
κi κi
42i
δεnκi
4
24
3.2. BOUNDING THE CHROMATIC NUMBER OF pe H,p
≤ε
2·log(b)n
2 log(β(n)).
The las inequali y can be p o ed as ollows. Le x:= β(n),c:= εlog(b)
4and
a:= 1 + ε
2−1
2−1. Then o su icien ly la ge x, we ha e xa≤c
log(x).
Now we a e eady o gi e an uppe bound o he expec ed alue o he ch oma ic
numbe o an augmen ed g aph.
Theo em 3.3 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o
some unc ion β:N→Nsuch ha β(n)→ ∞ o n→ ∞. Le u he p∈(0,1)
be cons an and b:= 1
1−p. Then o each ε > 0 he e is n(ε)∈Nsuch ha o all
n≥n(ε)
Eχpe H,p≤(1 + ε)·nlog(b)
2(log(n)−log(χ(H))).
P oo . Le Cdeno e he se o all colo classes o an op imal colo ing o Hand le
ε > 0. Addi ionally, we de ine o g(n) = β(n)(1+ ε
2)−1
2 he se o la ge colo classes
Lg={S∈ C||S| ≥ g(n)}and he se o small colo classes Sg=C Lgas in
Lemma 3.2. No e ha a se S∈ Sg∪Lgis an independen se in H, because Sis a
colo class o an op imal (p ope ) colo ing o H. So, he only edges in pe H,p[S]a e
he edges o Gn,p. We can hus iden i y pe H,p[S]wi h G|S|,p acco ding o Rema k 3.1.
Fu he mo e, since pis cons an he assump ions o Co olla y 2.6 a e ul illed o
su icien ly la ge n. Now
Eχpe H,p≤X
S∈C
Eχpe H,p[S]
=X
S∈Lg
Eχpe H,p[S]+X
S∈Sg
Eχpe H,p[S]
=X
S∈Lg
EχG|S|,p+X
S∈Sg
EχG|S|,p
| {z }
≤|S|
≤X
S∈Lg
EχG|S|,p+X
S∈Sg|S|
≤X
S∈Lg1 + ε
21
2·log(b)|S|
2 log(|S|)+X
S∈Sg|S|
( o su icien ly la ge nby Co olla y 2.6)
≤X
S∈Lg1 + ε
21
2·log(b)|S|
2 log(|S|)+ε
2·nlog(b)
2 log(β(n)) (Lemma 3.2)
≤1 + ε
21
2·log(b)
2·X
S∈Lg
|S|
log(g(n)) +ε
2·nlog(b)
2 log(β(n))
≤1 + ε
2·log(b)
2 log(β(n)) X
S∈Lg|S|
| {z }
≤n
+ε
2·nlog(b)
2 log(β(n))
31

3.2. BOUNDING THE CHROMATIC NUMBER OF pe H,p
≤(1 + ε)·nlog(b)
2 log(β(n))
=(1 + ε)·nlog(b)
2(log(n)−log(χ(H))).
We in oke he bounded di e ences inequali y o C. McDia mid [McD89]:
Theo em 3.4 (McDia mid’s inequali y) Le X1, . . . , Xnbe independen andom
a iables wi h Xj aking alues in some se Aj. Suppose ha some measu able
unc ion :Qn
j=1 Aj→Rsa is ies
| (x)− (x′)| ≤ cj
whene e he ec o s x, x′∈Qn
j=1 Ajdi e only in he j- h componen . Le Ybe he
( eal alued) andom a iable Y:= (X1, . . . , Xn). Then o any > 0
P(|Y−E(Y)| ≥ )≤2 exp −2 2
Pn
j=1 c2
j!.
Rema k 3.5 In o de o apply McDia mid’s inequali y o he ch oma ic numbe o
pe H,p, we i s se Xj:= {{i, j} ∈ E(pe H,p)|i<j}. Since he Xj o m a pa i ion
o he edges o pe H,p, he andom a iable χpe H,pdepends solely on he alues
o he Xj. We se
Y= (X1, . . . , Xn) = χpe H,p
he Xjbeing mu ually independen andom a iables. Fu he mo e, o each j, i
Xand ˆ
Xonly di e in he j- h componen , we ha e
 (X)− (ˆ
X)≤1,
since one addi ional colo will always be enough o colo he e ex j, i necessa y.
Thus, McDia mid’s inequali y is applicable wi h Pn
j=1 c2
j=nand we he ollowing
uppe bound o he ch oma ic numbe o pe H,p .
Theo em 3.6 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o some
unc ion β:N→Nsuch ha β(n)→ ∞ o n→ ∞. Le u he be p∈(0,1) and
b=1
1−p. Then we ha e o each ε > 0and su icien ly la ge n
χpe H,p≤(1 + ε)·nlog(b)
2(log(n)−log(χ(H))) a.a.s.
P oo . Le ε > 0and λ=nlog(b)
2(log(n)−log(χ(H))). Now by Theo em 3.3 and McDia mid’s
inequali y we ge
Pχpe H,p≥(1 + ε)·λ
=Pχpe H,p−1 + ε
2·λ≥ε
2·λ
32
3.2. BOUNDING THE CHROMATIC NUMBER OF pe H,p
≤Pχpe H,p−Eχpe H,p≥ε
2·λ(Theo em 3.3)
≤2 exp 
−2
n· ελ
2!2
(McDia mid’s inequali y)
≤2 exp 
−2
n· εn log(b)
4(log(n)−log(χ(H)))!2

=2 exp −ε2log(b)2n
8(log(n)−log(χ(H)))2!=o(1).
3.2.2 The Case p(n) = n−θ o some θ∈0,1
3
We conside now g aphs om pe H,p wi h non-cons an and small p. When ying
o apply he same s a egy as o cons an p, i u ns ou ha o small colo classes
i is no enough o me ely coun he numbe o e ices as in Lemma 3.2. The eason
is ha he numbe o e ices in small componen s can be o a highe o de han
he desi ed bound o he ch oma ic numbe o pe H,p. Ins ead we will use ano he
implica ion o a esul o Bollobás [Bol88].
This implies he ollowing esul which bounds he numbe o colo s needed o
colo he small colo classes o H.
Lemma 3.7 Le ε > 0and H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n)
o some unc ion β:N→Q. Le u he g(n) = β(n)
log(n)and le C he se o all
colo classes o an op imal colo ing o H. De ine Lg={S∈ C||S| ≥ g(n)}and
Sg=C Lg. Le u he n=n(ε)su icien ly la ge and p(n) = n−θ, whe e θ∈0,1
3
and b=1
1−p. I β(n)≥n3θ, hen we ha e o n≥n(ε) o some n(ε)∈N,
E χ pe H,p "[
C∈Sg
C#!!≤εnp
2(log(np)−log(χ(H))).
P oo . Acco ding o Rema k 3.1, o each C∈ Sgwe can iden i y pe H,p(n)[C]wi h
G|C|,p(n). So by in oking Co olla y 2.10 wi h ε=1
3we ge
Eχpe H,p(n)[C]=EχG|C|,p(n)
≤EχG|g(n)|,p(n) (since |C| ≤ g(n))
≤1 + 1
3g(n)p(n)
2 log(g(n)p(n)) (Co olla y 2.10)
=2
3
g(n)p(n)
log(g(n)p(n))
=2
3
β(n)p(n)
log(n)(log(β(n)p(n)) −log(log(n)))
≤2
3
β(n)p(n)
log(n)(1 −o(1)) log(β(n)p(n)) (since β(n)p(n)≥n2θ)
33
3.2. BOUNDING THE CHROMATIC NUMBER OF pe H,p
≤β(n)p(n)
log(n) log(β(n)p(n)).
Thus, since |Sg| ≤ χ(H)≤n
β(n)we ha e
Eχpe H,p [∪C∈SgC]≤X
C∈Sg
Eχpe H,p[C] (Lemma 2.11)
≤n
β(n)
β(n)p(n)
log(n) log(β(n)p)(|Sg| ≤ n
β(n))
=np(n)
log(n) log(β(n)p)
≤εnp
2 log(β(n)p)( o nla ge enough)
=εnp
2(log(np)−log(χ(H))).
Nex , we bound he expec a ion o χpe H,p om abo e using Lemma 3.7.
Theo em 3.8 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o
some unc ion β:N→Q. Le u he ε > 0and p(n) = n−θ, whe e θ∈0,1
3and
b=1
1−p. I β(n)≥n3(θ+δ) o some cons an δ > 0, hen he e exis s n(ε)∈Nso
ha o all n≥n(ε)we ha e
Eχpe H,p≤(1 + ε)·np
2(log(np)−log(χ(H))).
P oo . Le Cdeno e he se o all colo classes o an op imal colo ing o Hand
le ε > 0. Addi ionally we de ine o g(n) = β(n)
log(n) he se o la ge colo classes
Lg={S∈ C||S| ≥ g(n)}and he se o small colo classes Sg=C Lg.
Fo a la ge colo class S∈ Lgo an op imal colo ing o H he e a e no edges o
Hwi hin S. So we can iden i y pe H,p(n)[S]wi h G|S|,p(n),by Rema k 3.1. Since
|S| ≥ g(n) = β(n)
log(n)≥n3(θ+δ
2) o su icien ly la ge n, we ha e
p(n) = n−θ≥ |S|−θ
3(θ+δ/2) =|S|−1
3+δ
6(θ+δ/2) ,
and we may in oke Co olla y 2.10 wi h ε′=1 + ε
21
2−1>0and ge
Eχpe H,p[S]=EχG|S|,p(n)≤1 + ε
21
2p|S|
2 log(|S|p).(3.1)
Fo su icien ly la ge n, log(log(n)) ∈o ((log(β(n)))) .Thus
1 + ε
21
2log(g(n)) = 1 + ε
21
2(log(β(n)) −log(log(n))
| {z }
=o(log(β(n)))
)≥log(β(n)).(3.2)
34
3.2. BOUNDING THE CHROMATIC NUMBER OF pe H,p
Now
Eχpe H,p≤X
S∈C
Eχpe H,p[S](Lemma 2.11)
=X
S∈Lg
Eχpe H,p[S]+X
C∈Sg
Eχpe H,p[S]
=X
S∈Lg
EχG|S|,p+X
C∈Sg
EχG|S|,p (Rema k 3.1)
≤X
S∈Lg1 + ε
21
2p|S|
2 log(|S|p)+X
C∈Sg
EχG|S|,p (wi h (3.1))
≤X
S∈Lg1 + ε
21
2p|S|
2 log(|S|p)+ε
2·np
2 log(β(n)p)
(Lemma 3.7 o n≥n(ε) o some n(ε)∈N)
≤X
S∈Lg1 + ε
21
2p|S|
2 log(g(n)p)+ε
2·np
2 log(β(n)p)(|S| ≥ g(n))
=1 + ε
21
2pPS∈Lg|S|
2 log(g(n)p)+ε
2·np
2 log(β(n)p)
≤1 + ε
21
2pn
2 log(g(n)p)+ε
2·np
2 log(β(n)p)
≤1 + ε
2pn
2 log(β(n)p)+ε
2·np
2 log(β(n)p)(wi h (3.2))
= (1 + ε)pn
2(log(np)−log(χ(H)))
The main esul o his sec ion is he ollowing heo em, whe e we use McDi-
a mid’s bounded di e ences inequali y (Theo em 3.4) o bound he p obabili y ha
χpe H,pdi e s om i s expec a ion by a la ge amoun .
Theo em 3.9 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o
some unc ion β:N→Q.Le u he p(n)≥n−θ, whe e θ∈0,1
3and b=1
1−p. I
β(n)≥n3θ, hen
χpe H,p≤(1 + ε)·np
2(log(np)−log(χ(H))) a.a.s.
P oo . Le ε > 0and λ=εn log(b)
4(log(np)−log(χ(H))) .We ha e
P χpe H,p≥(1 + ε)nlog(b)
2(log(np)−log(χ(H)))!
=P χpe H,p≥1 + ε
2nlog(b)
2(log(np)−log(χ(H))) +λ!
≤Pχpe H,p≥Eχpe H,p+λ(Theo em 3.8)
35
3.3. TIGHTNESS OF UPPER BOUNDS FOR CERTAIN GRAPHS
≤2 exp −λ2
2n!(McDia mid’s inequali y, Theo em 3.4)
≤2 exp − ε2np2
32(log(n)−log(χ(H)))2!! (by Rema k 2.1 and log(np)≤log(n))
≤exp −n1
4,
and he las inequali y holds, because p≥n−θ,θ∈(0,1
3)implies np2≥n1/3.
3.3 Tigh ness o uppe bounds o ce ain g aphs
We p o ed an uppe bound o he ch oma ic numbe o an augmen ed g aph, de-
pending only on pand he ch oma ic numbe o he hos g aph. A na u al ques ion
is, o cou se, whe he ou bounds a e igh . Indeed, he nex heo em shows ha
he e exis hos g aphs o which he asymp o ics o he ch oma ic numbe is equal
o he asymp o ics o he uppe bound in Theo em 3.6. We will p o e his by consid-
e ing he independence numbe o a ce ain class o hos g aphs. These hos g aphs
a e cha ac e ized by a "low" numbe o "la ge" independen se s. As an example one
can conside he comple e χ(H)-pa i e g aphs.
Lemma 3.10 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o some
unc ion β=β(n)wi h β(n)→ ∞ as n→ ∞. Fu he le k=l2(log(n)−log(χ(H)))
log(b)m
and nH,k he numbe o independen se s o size kin H.
I nH,k ∈oχ(H)
n−k+1, hen α(pe H,p)≤2(log(n)−log(χ(H)))
log(b)a.a.s.
P oo . Le Xkbe he andom a iable ha coun s he numbe o independen se s
o size kin pe H,p. Now
Pα(pe H,p)≥k=P(Xk≥1)
≤E(Xk)(Ma ko ’s inequali y)
=nH,k(1 −p)(k
2)
=nH,k ·exp −log(b)
2k(k−1)!(b= (1 −p)−1)
≤nH,k ·exp −log(b)
2
2(log(n)−log(χ(H)))
log(b)(k−1)!
=nH,k · χ(H)
n!−k+1
=o(1),
wi h ou assump ion on nH,k.
Toge he wi h he well-known inequali y χ(G)≥n
α(G)Lemma 3.10 implies The-
o em 3.11:
36

3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL
CHROMATIC NUMBER
Theo em 3.11 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o
some unc ion β=β(n)wi h β(n)→ ∞as n→ ∞. Fu he le k=l2(log(n)−log(χ(H)))
log(b)m
and nH,k he numbe o independen kse s, in H.
I nH,k ∈oχ(H)
n−k+1, hen o each ε > 0 he e is a n(ε)∈N, so ha o all
n≥n(ε)we ha e
1. α(pe H,p)≤2(log(n)−log(χ(H)))
log(b)a.a.s.
2. χpe H,p≥(1 −ε)·nlog(b)
2(log(n)−log(χ(H))) a.a.s.
3.4 Colo ing Augmen ed G aphs wi h Hos G aphs
o small Ch oma ic Numbe
The p oo s o Theo em 3.6 and Theo em 3.9 ely on McDia mid’s bounded di e -
ences inequali y and a e no cons uc i e. In his sec ion we will gi e algo i hms
based on algo i hms o Bollobás [Bol88] (in he ollowing Algo i hm 2.1.1 and Algo-
i hm 2.1.3). They ind a colo ing o pe H,p wi h a mos (1 + ε)·nlog(b)
2(log(n)−log(χ(H)))
colo s a.a.s. We es ic ou sel es o hos g aphs Hwi h χ(H)≤n
log(n)γ o some
cons an γ≥1
2in he case ha pis cons an and hos g aphs wi h χ(H)≤n1−3θ−2δ
2
o some a bi a y small cons an δ > 0i p(n) = n−θ. In p epa a ion o he
es o he sec ion we de ine he se s o la ge and small colo classes analogously
o sec ion 3.2. The Algo i hms 3.4.1, 3.4.2, 2.1.1 and 2.1.3 ha e exponen ial ime
complexi y.
De ini ion 3.12 Le H= ([n], E)be a de e minis ic g aph. Le be a colo ing o
Hand C he se o all colo classes wi h espec o . Le u he g:N→Rbe a
unc ion. We de ine
Sg:= {S∈ C||S|< g(n)}and Lg:= {S∈ C||S| ≥ g(n)}.
Sgis he se o small and Lgis he se o la ge colo classes wi h espec o .
We will use Algo i hm 2.1.1 o colo he la ge colo classes o Hwhile Theo em 2.5
allows us o bound he p obabili y ha his app oach ails o yield a colo ing wi h
a small numbe o colo s. We use he ollowing algo i hm o cons uc a p ope
colo ing o pe H,p.
Algo i hm 3.4.1: Colo ing pe H,p
Inpu : A de e minis ic g aph Hwi h χ(H)≤n
β(n)whe e β(n)≥log(n)γ
o some cons an γ > 1
2, an augmen ed g aph G= pe H,p o some
cons an p∈(0,1) and ε > 0wi h ε < 2(2γ−1).
Ou pu : A p ope colo ing o Gusing less han (1 + ε)·nlog(b)
2(log(n)−log(χ(H)))
colo s.
1Cons uc an op imal colo ing χ′o H;
2In each colo class So χ′wi h |S| ≥ β(n)(1+ ε
2)−1
2=: g(n)cons uc a
p ope colo ing using Algo i hm 2.1.1;
3Colo each e ex ha is s ill uncolo ed wi h i s own colo ;
37
3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL
CHROMATIC NUMBER
Theo em 3.13 Le H= ([n], E)be a de e minis ic g aph wi h χ(H)≤n
log(n)γ o
some cons an γ > 1
2and le β(n) = n
χ(H). Le u he p∈(0,1) be cons an and
b=1
1−p. Then Algo i hm 3.4.1 a.a.s.cons uc s a p ope colo ing o pe H,p using
a mos (1 + ε)·nlog(b)
2(log(n)−log(χ(H))) colo s.
P oo . Since his algo i hm cons uc s a p ope colo ing, he only hing le o p o e
is ha i uses a mos (1 + ε)·nlog(b)
2(log(n)−log(χ(H))) colo s a.a.s.. We will show ha o
colo ing he la ge colo classes o Ha mos (1 + ε
2)·nlog(b)
2(log(n)−log(χ(H))) colo s a e
used a.a.s.. Since by Lemma 3.2 he e a e a mos ε
2·log(b)n
2 log(n) e ices o pe H,p le
uncolo ed, he o al numbe o colo s used is a mos as s a ed in he heo em.
Fo each S⊆[n], le ξ(pe H,p[S]) be he numbe o colo s ha we e used by
Algo i hm 3.4.1 o colo he e ices o S. Fi s we ecall some p elimina y ac s:
each S∈ Lgis an independen se in H hus pe H,p[S]can be iden i ied wi h
G|S|,p (see Rema k 3.1). Acco ding o Theo em 2.5, Algo i hm 2.1.1 uses mo e han
1 + ε
2log(b)n
2 log(n)colo s o colo Gn,p wi h p obabili y a mos exp −cn2
log(n)8 o some
cons an c > 0. No e ha he p obabili y pis cons an by he assump ion o he
heo em and hus he e m cp7 om Theo em 2.5 is cons an he e. Choose ε′>0
such ha 1+ε′=1 + ε
21
2.Combining hese ac s we ge o each colo class S∈ Lg
P ξpe H,p[S]≥1 + ε
21
2log(b)|S|
2 log(|S|)!
=P ξG|S|,p≥1 + ε
21
2log(b)|S|
2 log(|S|)!
=P ξG|S|,p≥(1 + ε′)log(b)|S|
2 log(|S|)!
≤exp −c|S|2
log(|S|)8!(3.3)
o some cons an c > 0.
We will use
χ(H) = n
β(n)≤n
log(n)1
2
and hus log(β(n)) ≥log log(n)1
2=1
2log(log(n)).
(3.4)
And con inue
P X
S∈Lg
ξpe H,p[S]≥1 + ε
2·log(b)n
2(log(n)−log(χ(H)))!
=P X
S∈Lg
ξpe H,p[S]≥1 + ε
2·log(b)n
2 log(β(n))!
≤P X
S∈Lg
ξpe H,p[S]≥1 + ε
21
2·log(b)PS∈Lg|S|
2 log(g(n)) !(since X
S∈Lg|S| ≤ n)
=P X
S∈Lg
ξpe H,p[S]≥X
S∈Lg1 + ε
21
2·log(b)|S|
2 log(g(n))!
38
3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL
CHROMATIC NUMBER
≤P X
S∈Lg
ξpe H,p[S]≥X
S∈Lg1 + ε
21
2·log(b)|S|
2 log(|S|)!(since g(n)≥ |S|)
≤X
S∈Lg
P ξpe H,p[S]≥1 + ε
21
2·log(b)|S|
2 log(|S|)!(union bound)
≤X
S∈Lg
exp −c|S|2
log(|S|)8!(by (3.3))
≤X
S∈Lg
exp −cg(n)2
log(g(n))8!(since x2
log(x)8is an inc easing unc ion)
≤χ(H)·exp −c·g(n)2
log(g(n))8!(since |Lg| ≤ χ(H))
≤n
β(n)·exp −c·g(n)2
log(g(n))8!
= exp log(n)−log(β(n)) −cg(n)2
log(g(n))8!
= exp 
log(n)−log(β(n)) −c′β(n)2(1+ ε
2)−1
2
log(β(n))8

( o some c′>0, since g(n) = β(n)(1+ ε
2)−1
2)
≤exp 
log(n)−γlog(log(n)) −c′′ log(n)γ2(1+ ε
2)−1
2
log(log(n))8
( o some c′′ >0by 3.4)
=o(1).(since γ≥1
2)
We p oceed o colo an augmen ed g aph, whe e p(n) = n−θ o some θ∈0,1
3.
We need he g eedy algo i hm Algo i hm 2.1.2 o colo he small colo classes.
Based on hese esul s we use he ollowing algo i hm.
Algo i hm 3.4.2: A colo ing o pe H,p
Inpu : A cons an θ∈0,1
3, an edge p obabili y pwi h p=p(n) = n−θ, a
de e minis ic g aph Hwi h χ(H)≤n
β(n)whe e β(n)≥n3θ
2+δ o
some δ > 0a bi a y, bu ixed and a pe u bed g aph G= pe H,p.
Fu he an ε > 0a bi a y small bu ixed.
Ou pu : A p ope colo ing o Gusing less han (1 + ε)·nlog(b)
2(log(n)−log(χ(H)))
colo s.
1Cons uc an op imal colo ing χ′o H;
2In each colo class So χ′wi h |S| ≥ β(n)
log(n)=: g(n)cons uc a p ope
colo ing using Algo i hm 2.1.3;
3Colo each emaining colo class o Hwi h he g eedy algo i hm
Algo i hm 2.1.2;
Theo em 3.14 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = n
β(n) o
some unc ion β:N→Qsuch ha β(n)→ ∞ o n→ ∞. Le u he be
39
3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL
CHROMATIC NUMBER
p=p(n) = n−θ o some cons an θ∈(0,1
3), le b=1
1−pand ε > 0. I β(n)≥
n3θ+ε, Algo i hm 3.4.2 a.a.s.cons uc s a p ope colo ing o pe H,p wi h a mos
(1 + ε)nlog(b)
2(log(n)−log(χ(H))) colo s.
P oo . Le ξ(pe H,p)be he numbe o colo s used by Algo i hm 3.4.2. Since his
algo i hm yields a p ope colo ing, i is le o p o e ha
ξ(pe H,p)≤(1 + ε)nlog(b)
2(log(n)−log(χ(H))) a.a.s.
Wi h g=g(n) = β(n)
log(n)we conside Sgas well as Lg. We spli ou p oo in o
wo pa s. Fi s we p o e ha all "small" colo classes a e colo ed using a mos
ε
2
nlog(b)
2(log(n)−log(χ(H))) colo s. Nex we will p o e ha all "la ge" colo classes a e colo ed
wi h a mos 1 + ε
2nlog(b)
2(log(n)−log(χ(H))) colo s.
Claim 1: ξ(pe H,p [SS∈SgS]) <ε
2
nlog(b)
2(log(n)−log(χ(H))) a.a.s.
P oo o Claim 1: Le χg(Gn,p)be he numbe o colo s ha a e used when
colo ing Gn,p wi h he g eedy Algo i hm 2.1.2. Since o each S∈ Sg he g aph
pe H,p[S]has he same dis ibu ion as he andom g aph G|S|,p(n)by Rema k 3.1.
We may conside he andom g aph Gg(n),p(n)in which each se o |S| e ices induces
aG|S|,p(n). Thus, he g eedy algo i hm uses a leas as many colo s o colo Gg(n),p(n)
as o pe H,p[S].Since Algo i hm 3.4.2 uses he g eedy Algo i hm 2.1.2 o colo S,
we ge ξ(pe H,p[S]) = χg(G|S|,p(n))whe e χg(G|S|,p(n))is he numbe o colo s used
by Algo i hm 2.1.2 o colo G|S|,p(n).
Thus o all q∈Rwe ha e,
Pξ(pe H,p(n)[S]) ≥q=Pχg(G|S|,p(n))≥q≤Pχg(Gg(n),p(n))≥q.(3.5)
Now
P





ξ pe H,p "[
S∈Sg
S#!≥ε
2·nlog(b)
2(log(n)−log(χ(H)
| {z }
=log(β(n))
))






≤P X
S∈Sg
ξ(pe H,p[S]) ≥ε
2·nlog(b)
2 log(β(n))!
≤P X
S∈Sg
ξ(pe H,p[S]) ≥ε
2·PS∈Sgβ(n) log(b)
2 log(β(n)) !(n≥PS∈Sgβ(n))
≤X
S∈Sg
P ξ(pe H,p[S]) ≥ε
2·β(n) log(b)
2 log(β(n))!(by Lemma 2.12)
≤X
S∈Sg
P χg(Gg(n),p)≥ε
2·β(n) log(b)
2 log(β(n))!(by inequali y 3.5)
≤X
S∈Sg
P χg(Gg(n),p)≥(1 + ε)·g(n) log(b)
2 log(g(n))!(g(n) = β(n)
log(n))
≤nexp −cg(n)3≤exp(−cn2) = o(1).(by Theo em 2.7)
40
4.2. BOUNDING THE CHOICE NUMBER OF RANDOMLY AUGMENTED
GRAPHS
Thus,
P X ≤1 + ε
2·|Vi|log(b)
2·log(|Vi|)!
=P X ≤E(X )−ε
2·|Vi|log(b)
2·log(|Vi|)!(by equa ion 4.1)
≤P X −E(X )≤ −ε|Vi|log(b)
4·log(|Vi|)!
≤P X −E(X )≤ −εg(n) log(b)
4·log(g(n))!
(since x/ log(x)is mono onously inc easing)
≤exp −2·ε2g(n)2log(b)2
16 log(g(n))2·2(log(n)−log(χ(H)))
(1 + ε)nlog(b)!(by (4.2))
= exp −ε2log(b)
4(1 + ε)·g(n)2
log(g(n))2·(log(n)−log(χ(H)))
n!
= exp −ε2log(b)
4(1 + ε)·n2(1−γ)(1+ε)−1
(1 + ε)−2(log(n)−log(χ(H)))2·(log(n)−log(χ(H)))
n!
= exp −ε2log(b)(1 + ε)
4·n2(1−γ)(1+ε)−1−1
(log(n)−log(χ(H)))!
= exp −ε2log(b)(1 + ε)
4(1 −γ)·n2(1−γ)(1+ε)−1−1
log(n)!(as χ(H) = nγ)
= exp −c1·n2(1−γ)(1+ε)−1−1
log(n)!( o some cons an c1>0)
≤exp(−c1nc2)
o some cons an c2>0,since γ < 1
2and ε < 2(1 −γ)−1.
Thus
P ∃Vi∈ Lg:∃ ∈Vi∧X ≤1 + ε
2|Vi|log(b)
2 log(|Vi|)!
≤X
Vi∈LgX
∈Vi
P X ≤1 + ε
2|Vi|log(b)
2 log(|Vi|)!(Union Bound)
≤nexp (−c1nc2)
=o(1).
So, wi h posi i e p obabili y, o e e y e ex ha belongs o a la ge colo class
Vi∈ Lgo Ha leas 1 + ε
2|Vi|log(b)
2 log(|Vi|)colo s a e assigned.
P oo o Theo em 4.1. By Lemma 4.4, wi h posi i e p obabili y o each e ex in a
la ge colo class Vi∈ Lgo Ha leas 1 + ε
2·|Vi|log(b)
(log(n)−log(χ(H))) colo s a e assigned.
By he p obabilis ic me hod he e exis s a unc ion ˆ
:U→ C such ha o each
Vi∈ Lgand each ∈Viwe ha e |ˆ
−1(Vi)∩U | ≥ 1 + ε
2·|Vi|log(b)
(log(n)−log(χ(H))) and
ˆ
−1(Vi)∩ˆ
−1(Vj) = ∅ o all i=j.
47

4.2. BOUNDING THE CHOICE NUMBER OF RANDOMLY AUGMENTED
GRAPHS
Since each Viinduces a G|Vi|,p and |Vi| ≥ g(n), he p obabili y ha Vidoes no
ha e a lis colo ing using only he colo s assigned o i by ˆ
is a mos exp −cg(n)2
log(g(n)8)
by Theo em 2.14. This implies ha he p obabili y ha he e exis s a Vi∈ Lg ha
does no ha e a lis colo ing using only he colo s andomly a ibu ed o i by , is
a mos
P ∃Vi∈ Lg:χlpe H,p[Vi]≥1 + ε
2·|Vi|log(b)
(log(n)−log(χ(H)))!
(by he union bound)
≤X
Vi∈Lg
P χlpe H,p[Vi]≥1 + ε
2·|Vi|log(b)
(log(n)−log(χ(H)))!
=X
Vi∈Lg
P χlG|Vi|,p≥1 + ε
2·|Vi|log(b)
(log(n)−log(χ(H)))!
≤X
Vi∈Lg
exp −cg(n)2
log(g(n)8)!(by Theo em 2.14)
≤χ(H) exp −cg(n)2
log(g(n)8)!(since |Lg| ≤ χ(H))
≤exp log(n)−n2(1−γ)(1+ε)−1
8 log(n)!=o(1).
As shown abo e, o each Vi∈ Lg he e exis s a colo ing φi:Vi→Uo pe H,p[Vi]
using only colo s assigned o Viby ˆ
a.a.s. We combine hese colo ings by se ing
φLg( ) = φVi( ) o each ∈Vi.Since ˆ
maps each colo o exac ly one colo class, no
wo neighbo s can ha e he same colo s wi h espec o φLg.This implies ha φLgis a
p ope colo ing o he la ge colo classes which uses a mos 1 + ε
2·nlog(b)
(log(n)−log(χ(H))).
A e ha ing colo ed he la ge colo classes, o each ∈V he e a e a leas
ε
2·nlog(b)
(log(n)−log(χ(H))) colo s in U ha ha e no ye been used. We conside he bipa i e
g aph Gb= (A˙
∪B)wi h he e ices o pe H,p ha a e in small colo classes o C
on one side, i.e. A={ ∈V:∃Vi∈ S ∈Vi}and he colo s ha a e no used by
φLgon he o he side, i.e. B={c∈U∧c /∈Im (φLg)}.Fo e e y e ex ∈A
and colo c∈Bwe add he edge { , c}i c∈U .As shown in Lemma 3.2 a mos
ε
2·nlog(b)
(log(n)−log(χ(H))) e ices emain uncolo ed. This implies
|A| ≤ ε
2·nlog(b)
(log(n)−log(χ(H)))
Fu he mo e, o each ∈Awe ha e
|NGb( )|≥|U |−|Im (Lg)| ≥ ε
2·nlog(b)
(log(n)−log(χ(H)))
because φLgused a mos 1 + ε
2·nlog(b)
(log(n)−log(χ(H))) colo s. So, o e e y ∅ =A′⊆A
and ∈A′we ha e
|NGb(A′)| ≥ |NGb( )| ≥ ε
2·nlog(b)
(log(n)−log(χ(H))) ≥ |A|≥|A′|
48
4.3. REMARKS ON TIGHTNESS
Thus by he use o Hall’s Ma iage Theo em he e exis s a Ma ching M ha co e s
A. The ma ching Minduces a lis colo ing φSgwi h espec o U o he e ices in
small colo classes using only he emaining colo s in he ollowing sense φSg( ) = c
i { , c} ∈ M.
Since φSgand φLguse disjunc se s o colo s, we de ine he ollowing p ope lis
colo ing o pe H,p wi h espec o U.
φ:V→U, 7→ 


φLg( ),∃Vi∈ Lg: ∈Vi
φSg( ),∃Vi∈ Sg: ∈Vi
4.3 Rema ks on igh ness
A e p o ing an uppe bound o χlpe H,p o he cases in which p∈(0,1) is
cons an and χ(H)< nγ o some γ < 1/2,we will in es iga e whe he o some
combina ions o Hand p he bound in Theo em 4.1 is igh . Ou i s ema k
conside s hos g aphs o small ch oma ic numbe .
Lemma 4.5 Le Hbe a de e minis ic g aph such ha χ(H)is bounded by a con-
s an . Then o all cons an p∈(0,1) and ε > 0we ha e
χlpe H,p≥nlog(b)
2 (log(n)−log(χ(H))) a.a.s.
P oo . Finding a p ope k-colo ing o a g aph Gis equi alen o inding a p ope
lis -colo ing o Gwi h espec o he amily U={[k]} ∈V,so χ(G)≤χl(G).The
well-known esul χ(G)≤n/α(G)combined wi h a esul o Bollobás and E dős
[BE76] ha says α(Gn,p)≤2 log(b)−1(1 −ε)−1/2log(n)a.a.s., we ge
q(1 −ε)nlog(b)
2 log(n)≤n
α(Gn,p)≤χ(Gn,p)≤χl(Gn,p)a.a.s.
By assump ion o he lemma χ(H)is bounded by a cons an , so log(χ(H)) ∈
o (log(n)) and he e exis s nε∈Nsuch ha o all n≥nε
(1 −ε)−1/2(log(n)−log(χ(H))) ≥log(n).
This implies o all n≥nε
(1 −ε)nlog(b)
2(log(n)−log(χ(H))) ≤q(1 −ε)nlog(b)
2(1 −ε)−1/2(log(n)−log(χ(H)))
≤q(1 −ε)nlog(b)
2 log(n)≤χlpe H,p.
49
4.4. CONCLUSION
The ollowing esul shows ha he bound in Theo em 4.1 is indeed igh in he
ollowing sense:
Theo em 4.6 Le H= ([n], E)be a de e minis ic g aph wi h χ(H) = nγ o some
γ < 1/2.Fu he le k=l2(log(n)−log(χ(H)))
log(b)mand nH,k he numbe o independen k
se s, in H.
I nH,k ∈oχ(H)
n−k+1, hen o each ε > 0 he e is a nε∈N, so ha o all
n≥nεwe ha e
χlpe H,p≥(1 −ε)·nlog(b)
2(log(n)−log(χ(H))) a.a.s.
P oo . Since χ(H) = nγ he p e equisi es o Theo em 3.11 a e sa is ied.
This implies
χlpe H,p≥χpe H,p≥(1 −ε)·nlog(b)
2(log(n)−log(χ(H))) a.a.s.
4.4 Conclusion
In his chap e we p o ed ha o hos g aphs Hwi h ch oma ic numbe χ(H)≤nγ,
o some γ < 1/2and p∈(0,1) cons an , he ch oma ic numbe o he andomly
augmen ed g aph pe H,p is a.a.s. bounded om abo e by
χlpe H,p≤nlog(b)
2(log(n)−log(χ(H))).(4.3)
This is he same uppe bound ha was p o ed o he ch oma ic numbe in Chap-
e 3. Fu he mo e, we p o ed ha his bound is igh o ce ain hos g aphs ha
con ain only ew independen se s o a ce ain size. All o hese esul s show ha
χlpe H,pin hese cases beha es in he same way as χpe H,p.
The ollowing na u al ques ions a ise:
Ques ion 1 : Does he uppe bound in 4.3 hold o all andomly augmen ed
g aphs pe H,p as long as p∈(0,1) is cons an and Hsa is ies χ(H)∈o (n)?
Ques ion 2 : Fo which combina ions o hos g aphs Hand p obabili y unc-
ions p:N→(0,1) can a simila bound be shown?
Ques ion 3 : Can he echnique used in his chap e be used o show simila
bounds o ela ed in a ian s? We sugges he game ch oma ic numbe and he
quan um ch oma ic numbe as na u al candida es.
50
Chap e 5
An Algo i hm o win he biased
k-Edge-Connec i i y and k-Fac o
Games as
5.1 In oduc ion
5.1.1 P e ious wo k
The biased Make -B eake -Connec i i y game was i s in oduced by Ch á al and
E dős [CE78]. They p o ed he ollowing uppe bound o i s c i ical bias.
Theo em 5.1 (Ch á al and E dős, [CE78]) Le ε > 0, hen he e exis s n(ε)∈N,
such ha o each n≥n(ε)and b > (1+ε)n
log(n),B eake wins he (1−b)connec i i y
game.
This is achie ed by isola ing a single e ex ∈V, i.e. assu ing ha a he end o
he game i s Make deg ee is ze o and i s B eake deg ee is n−1.Since Hamil onici y
implies connec i i y, his also implies ha B eake wins he Hamil onici y game,
and mos o he games ha equi e Make o build a global s uc u e, wi h he
same pa ame e s. K i ele ich [K i10] p o ed he ollowing heo em o he biased
Hamil onian cycle game de e mining he asymp o ically exac c i ical bias o his
game o be (1 + o(1)) n
log(n).
Theo em 5.2 (K i ele ich 2010, [K i10]) The e exis s n0∈Nsuch ha o e -
e y n∈N≥n0Make has a s a egy o win he (1 : b)Hamil onian cycle game
played on he comple e g aph on n e ices in a mos 14n ounds o e e y b≤
1−30
log1/4(n)n.
This esul is achie ed in h ee s eps. In he i s s ep an expande g aph is
c ea ed by Make . In he second s ep he connec ed componen s o he expande
g aph a e connec ed by Make and a connec ed expande is achie ed. In he las
s ep, he Hamil onian cycle is comple ed by adding boos e s o Make ‘s g aph.
K i ele ich also ema ks ha his s a egy can be gene alized. We emind he
eade o Theo em 2.15.
51
5.1. INTRODUCTION
Theo em 5.3 (Theo em 2.15) Le ε > 0and k∈N.The e exis s n0∈Nsuch ha
o e e y n∈N≥n0Make has a s a egy o cons uc kedge disjoin Hamil onian
cycles in he (1 : b)game played on he comple e g aph on n e ices in a mos
min(13n, (8k+ 1)n) ounds o e e y b≤(1 −ε)n.
We now conside a g aph G= (V, E)in which Eis he pai wise disjoin union
o kHamil onian cycles. Then each e ex ∈Vhas deg ee exac ly 2k. Thus G
is a 2k- ac o . Fu he mo e, o wo dis inc e ices , w ∈V he e exis 2kedge
disjoin pa hs connec ing , w. This is ue because each Hamil onian cycle induces
wo pa hs om o w. The echniques o K i ele ich yield a lowe bound o he
c i ical bias in he (1 : b) 2k-edge-connec i i y game and in he (1 : b) 2k- ac o
game and show ha bo h games can be won in a linea numbe o ounds.
Since he c i ical bias is known asymp o ically, i is u he o in e es how many
ounds Make has o play o claim a winning g aph. We no e he ollowing:
Rema k 5.4 (Lowe Bound) A Hamil onian g aph has o con ain a Hamil onian
cycle, which con ains exac ly nedges. Since Make can only add one edge pe
ound, Make canno win in ewe han n ounds.
Fo k≥2,i Gis k-edge-connec ed, i s minimum deg ee has o be a leas k.
O he wise i would be possible o des oy i s connec i i y by emo ing e e y edge
inciden in a e ex wi h deg( )< k. Since e e y edge connec s exac ly o e ices,
he minimum numbe o edges needed is lk
2nm.Since Make can add only one edge
pe ound, Make canno win in ewe han lk
2nm ounds.
Fo he case k= 1 B üs le e al. [BCN+23] showed he ollowing imp o emen
o K i ele ich‘s esul .
Theo em 5.5 (B üs le e al. 2023, [BCN+23]) The e exis s a cons an C > 0and
n0∈Nsuch ha o any b < n
log(n)−Cn
log(n)3/2and n≥n0Make wins he (1 : b)
Hamil on cycle game on he comple e g aph on n e ices in a mos n+Cn
√log(n)
ounds.
5.1.2 Ou esul s
Rema k 5.6 Since an edge disjoin union o kHamil onian cycles consis s o kn
edges, Make needs a leas kn ounds o win his (1 : b)game. Thus o he case
k= 1,Theo em 5.5 s a es essen ially he as es possible ound-complexi y, up o
he Cn
√log(n)=o(n) e m. Analogously, ou main heo em gi es he as es ound-
complexi y, up o an o(n) e m in he k-edge-connec i i y game and he 2k- ac o
game:
Theo em 5.7 (Main Theo em) Le k∈Nbe a bi a y bu ixed. The e exis s a
cons an Ck>0and n0∈Nsuch ha o any b < n
log(n)−Ckn
log(n)3/2and n≥n0Make
has a s a egy o cons uc kedge disjoin Hamil onian cycles in he (1 : b)game on
he comple e g aph on n e ices in a mos kn +Ckn
√log(n) ounds.
The main heo em immedia ely implies a ew addi ional esul s:
52

5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES
Theo em 5.8 Le k∈Nbe a bi a y bu ixed. The e exis s a cons an Ck>0and
n0∈Nsuch ha o any b < n
log(n)−Ckn
log(n)3/2and n≥n0Make has a s a egy o win
(1 : b)k- ac o -game on he comple e g aph on n e ices in a mos lk
2mn+Ckn
√log(n)
ounds.
P oo o Theo em 5.8. I kis e en, Make builds k
2Hamil onian cycles wi h he
algo i hm used in he p oo o he main heo em Theo em 5.7 and hese cycles
o m a k- ac o . I kis odd, Make builds k+1
2=lk
2mHamil onian cycles wi h
he algo i hm used in he p oo o he main Theo em and hen chooses one o he
Hamil onian cycles o emo e e e y second e ex in i . By his dele ion p ocess,
we ha e c ea ed a k- ac o .
Theo em 5.9 Le k∈N≥2be a bi a y bu ixed. The e exis s a cons an Ck>0
and n0∈Nsuch ha o any b < n
log(n)−Ckn
log(n)3/2and n≥n0Make has a s a egy
o win he (1 : b)k-edge-connec i i y-game on he comple e g aph on n e ices in
a mos k
2+Ckn
√log(n) ounds.
5.1.3 Me hods and Inno a ions
In his chap e we use echniques ha a e simila o hose used in a pape o B üs le
e al. [BCN+23] ha gi es an algo i hm o win he (1 : b)Hamil onian cycle game in
asymp o ically op imal ime. Since, in con as o B üs le e al., we a e in e es ed in
building mul iple edge-disjoin Hamil onian cycles, we ha e o build he ounda ion
o hese cycles simul aneously. Whe e B üs le e al. buil a single se o pa hs ha
will be joined o o m he single Hamil onian cycle, we build kedge disjoin se s o
pa hs o di e en colo s simul aneously.
As in [BCN+23] we use an expande -like subse o V o acili a e o a ions simila
o hose in oduced by Pósa [Pó76]. Howe e , since we wan o cons uc k≥1edge-
disjoin Hamil on cycles, we canno use hese edges in mul iple Hail on cycles. Thus
we inc ease he equi ed minimum deg ee o hese e ices o 34kwhe e B üs le e
al. only equi ed a minimum deg ee o 10.
This inc ease in he minimum deg ee also ensu es ha he expande -like subse
emains connec ed and keeps expande -like p ope ies e en i all kHamil onian
cycles we e emo ed a he end o he game.
In addi ion o hese modi ica ions we p esen an inno a i e s a egy ha en-
su es k-connec i i y based on he s uc u e ha a ises a he end o he algo i hm
Hamil on-Cycles.
5.2 Desc ibing he Algo i hm Hamil on-Cycles
In he algo i hm Hamil on-Cycles we encoun e cases in which one e ex is de e -
mined i s and Make is supposed o add an edge o his e ex. Since some o ou
p oo s ely on he ac ha a ce ain amoun o andom edges we e added o each
e ex o a ce ain subse o V, we wan o "igno e" he edges which a e inciden
in bu we e chosen om some w∈V { }.To achie e his we conside some
edges o be di ec ed edges. Whene e we call o Make o claim he di ec ed edge
53
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES
( , w),Make chooses he edge { , w}and deno es ha he di ec ed edge ( , w)was
supposed o be aken. Howe e , his is only a bookkeeping measu e. This app oach
leads o he ollowing p oblem:
Le , w ∈V. Wha is Make supposed o do i he algo i hm Hamil on-Cycles
calls o he addi ion o he di ec ed edge ( , w),bu { , w}was al eady claimed as
he di ec ed edge (w, )? This is easily emedied. Whene e his is he case Make
upda es he bookkeeping by including he di ec ed edge (w, ).Since Make did
no ha e o claim an edge (as {w, }={ , w}had al eady been chosen), Make
akes ano he u n acco ding o he algo i hm Hamil on-Cycles immedia ely wi h
an upda ed ou -deg ee o .
We de ine he deg ee in B eake s g aph o some ∈Vas dB( ).We call a e ex
∈V oublesome i dB( )≥n
√log(n).We u he de ine he numbe o ou -edges
Make added o a e i became oublesome as d∗
M( )and he numbe o ou -edges
Make added o be o e i became oublesome as d′
M( ).Fu he we de ine in each
s ep o e e y ∈V, dang( ) := dB( )−bd∗
M( ).These no a ions a e consis en
wi h [BCN+23].
In he i s s age we c ea e a se Sio size On
√log(n)and a se Pio amilies
o pa hs in V Si.We also make su e ha he pa hs a e no oo long i.e. each
such pa h has a leng h o a mos log(n).The ele ance o bounding he leng h will
become appa en in S age 3, when we wan o connec he e ices o he pa hs
o ensu e connec i i y. Fo cla i y we colo all edges ha a e picked wi h a colo
be ween 0and k, whe e edges colo ed wi h a colo i, 1≤i≤kwill be used o o m
he i- h Hamil onian cycle, while he edges colo ed wi h 0a e all-pu pose edges no
ye commi ed o one o he Hamil onian cycles.
We call , w ∈V Sij-neighbo s, i hey a e joined by an edge o colo j. Fo
each ound i, colo j∈[k]and ∈V Si,we de ine [ ](j)
i o be he pa h o colo j
ha con ains .
A he beginning we choose S0⊆Va bi a y wi h S0=1000(4k+3)2√k+2n
√log(n),and
o each j∈[k]we de ine P(j)
0 o be he se o all single on pa hs in V S0,whe e a
single on pa h consis s o one e ex only.
5.2.1 S age 1: C ea ing a G aph consis ing o an Expande
and ew pa hs
I , a e ound io B eake a e ex ∈V Sihas become oublesome, i is added
o Si−1and o each j, we dele e he pa h [ ](j)
i−1=P1◦ ◦P1 ha con ains , om
P(j)
i.Fu he mo e, all Make -edges inciden in a e ecolo ed wi h k+1.The ea e
he pa hs P1and P2a e added o P(j)
i.
Two pa hs P, P′∈ Pj
io leng h less han log(n)a e called (u, )-a ailable in Pj
i
i uis an endpoin o P, is an endpoin o P′,{u, }is s ill unclaimed and no edges
o colo k+ 1 a e inciden in uo . This implies ha un il his poin he e was a
mos one edge o colo jinciden in uand a mos one edge o colo jinciden in .
Case 1: E e y oublesome e ex xsa is ies d∗
M(x)≥34k.
54
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES
Case 1.1: The e exis s a non- oublesome e ex ∈Si−1wi h d′( )<
34k, hen
•choose w∗∈ {w∈S0: ( , w)/∈B∪M}uni o mly a andom, add
( , w∗) o Mand colo i wi h 0.
•Se Si=Si−1and Pi=Pi−1.
Case 1.2: E e y non- oublesome e ex in Si−1has a deg ee o d′
M( )≥
34k. We ha e wo cases:
Case 1.2.1: The e a e wo elemen s Pand P′in some P(j)
i−1 ha a e
(u, )-a ailable. Then:
•Choose Pand P′ om P(j)
i−1which a e (u, )a ailable such ha
P(j)
i−1is minimal wi h espec o j.
•Add {u, } o Mand colo i wi h j.
•Se Si=Si−1and P(j)
i=P(j)
i−1−P−P′+P∗whe e P∗is he
pa h P∗=P◦(u, )◦P′.
Case 1.2.2: Else end s age 1, mo e o s age 2, and se i∗
0=i−1.
Case 2: The e is a oublesome e ex ∈Si−1such ha d∗
M( )<34k. Selec
o be a oublesome e ex ∈Si−1such ha d∗
M<34k, ha ing maximum
dange (wi h a bi a ily b oken ies). Then we ha e wo cases:
Case 2.1: I he e is no w∈V−Si−1such ha ( , w)is unclaimed, se
i∗
0=iand he game ends.
Case 2.1: O he wise
•choose such a wand claim ( , w)and colo i wi h 0;
•se Si=Si−1∪{w}and o each j∈[k]se Pj
i o be he se ob ained
om Pj
i−1by dele ing he pa h P ha con ained wand adding he
componen s o P−wand ecolo all j-edges inciden in wi h k+ 1.
5.2.2 S age 2: Closing kHamil on Cycles
S age 2 will be epea ed un il Make has c ea ed kedge disjoin Hamil onian cycles.
To s a each i e a ion se l∈[k]such ha l−1is he numbe o monoch oma ic
Hamil onian cycles al eady cons uc ed. We call an edge o colo j < l p o ec ed.
These edges will no longe be ecolo ed by ou algo i hm.
Fo no a ional ease le Eibe he se o endpoin s o pa hs in P(l)
iand S′
i:= Si∪Ei.
Le u he Mi:= {e∈M:c(e)∈ {0, l}}.Now le P(l)
i∗
lbe he longes pa h in Ml
ha only uses edges in Mi∗
land co e s a leas one e ex o S′
i∗
l.Make builds a
sequence o pa hs P(l)
i∗
l, P(l)
i∗
l+1, . . . such ha V(P(l)
i)⊆V(P(l)
i+1)and P(l)
i+1 is he longes
pa h ha uses only edges in Ml.
Case 1: E e y oublesome e ex xhas a deg ee o d∗
M(x)≥34k.
Case 1.1: The e is a non- oublesome e ex ∈Si−1wi h d′
M( )<34k.
Then
55
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES
•choose w∗∈ {w∈S0: ( , w)/∈B∪M}uni o mly a andom, add
( , w∗) o Mand se c({ , w}) = 0;
•se Si=Si−1and Pi=Pi−1.
Case 1.2: E e y non- oublesome e ex in Si−1has a deg ee o d′
M( )≥
34k. Then
Case 1.2.1: The e is some endpoin ∈ Eio an l-colo ed pa h, which
sa is ies d′
M( )<34k. Then
•choose w∗∈ {w∈S0: ( , w)/∈B∪M}uni o mly a andom,
add ( , w∗) o Mand se c({ , w∗}) = j.
•se Si=Si−1and Pi=Pi−1.
Case 1.2.2:(P olonga ion o Piusing o a ions)
E e y ∈ Eisa is ies d′
M( )≥34k.
Case 1.2.2.1: The e is no cycle o Mlwi h e ex se V(Pi)bu
he e exis s a pa h o Miwi h e ex se V(P(l)
i)and endpoin s
u, in S′
isuch ha {u, }is unclaimed,
•add (u, ) o Mand se c({u, }) = j;
•se Si=Si−1and P(l)
i=P(l)
i−1.
Case 1.2.2.2: Else
•i he e is a Hamil on cycle H⊆Ml,
– o each edge eon Hse c(e) = l, p o ec H, se l←l+ 1,
and i∗
l=i−1.
–Now i l=k+ 1 end he game. O he wise epea s age 2
wi h he upda ed alues.
•O he wise end he game epo ing ailu e.
Case 2: The e is a oublesome e ex ∈Si−1such ha d∗
M( )<34k. Selec
o be a oublesome e ex ∈Si−1such ha d∗
Ml<34k, ha ing maximum
dange (wi h a bi a ily b oken ies). Then
Case 2.1: The e is no w∈V−Si−1such ha ( , w)is no in B∪M, hen
se i∗
1=iand end he game.
Case 2.2: O he wise
•choose such a w, add ( , w) o Mand se c({ , w}) = 0;
•se Si=Si−1∪{w}and o each j∈[k]se Pj
i o be he se ob ained
om Pj
i−1by dele ing he pa h P ha con ained wand adding he
componen s o P−w.
Rema k 5.10 Le j∈[k].No e ha pa hs in P(j)only g ow i case 1.2.1 applies
and wo a ailable pa hs a e connec ed. Since pa hs a e only a ailable i bo h hei
leng hs a e a mos log(n).Thus in each s ep each elemen o P(j)a e o leng h a
mos log(n).
56
5.4. VERIFYING MAKER’S STRATEGY
This equi es ha Make keeps ack o he edge ha a e al eady ea ma ked o a
speci ic Hamil on cycle by building he P(j)as edge disjoin . This app oach u he
equi es ha he Sido no lose hei connec edness and expande -like p ope ies
a e he edges o a mos 2kedges a e "p o ec ed" in each e ex. This will be
achie ed by inc easing he Make ou -deg ee o e ices in Si.
Assume ha l∈[k]is he ac i e colo du ing u n i≥i∗
0. Recall ha S′
iis he
union o Siand all endpoin s o pa hs in P(l)
i. Fu he S0⊆Vwas chosen a he
beginning o he algo i hm Hamil on-Cycles a bi a y wi h
|S0|=



1000(4k+ 3)2√k+ 2n
qlog(n)


≥2004n
qlog(n)(5.1)
Fo each Z⊆S′
ide ine
N′(Z) := { ∈Si Z:∃u∈Zs. ., he edge (u, )was chosen by Make
and c((u, )) = 0}.
Lemma 5.23 Conside i≥i∗such ha Case 1.2.2 applies. Then wi h p obabili y
1−o (1) o e e y se S⊆Si ha con ains no oublesome e ices and ha sa is ies
|S| ≤ |Si|
2,we ha e
|N′(S)|>min |Si|
2−|Z|,2k+ 1
30k−1|Z|!,
i a mos 2kou -edges ha e been emo ed om each e ex in S.
P oo . Le Z⊆Siwi h |Z| ≤ |Si|
2.No e ha by Co olla y 5.21, and he chosen
ca dinali y o S0,
|Si|
2≤|S |
2≤1001 |S0|
2000 .(5.2)
Case 1 : |Z| ≥ |S0|
4.
Conside a e ex ∈Sand an a bi a y se o 32k0-colo ed ou -edges inciden in
. No e ha hese edges ha e been chosen in case 1.1 o ei he s age. This choice
was made uni o mly a andom be ween all e ices w∈S0,such ha ( , w)was
unclaimed. Le u he B⊆S0 |Z|wi h |B|=j|Si|
2k−Z. Le A ,i ⊆S0be he se
o all e ices wsuch ha { , w}was unclaimed by ei he playe in u n i. Since
is no oublesome, a mos n
√log(n)B eake edges a e inciden in . Fu he mo e, a
mos 34k≤n
√log(n)Make -edges a e inciden in . This implies |A ,i| ≥ |S0|− 2n
√log(n).
Thus, he p obabili y ha each edge chosen om (in some s ep in which Case
1.1 applied) ends in B∪Z, is a mos
|B∪Z|
|A|!32k
≤

|B|+|Z|
|S0|− 2n
√log(n)



32k
≤

|Si|
2(|S0|− 2n
√log(n))


32k
63

5.4. VERIFYING MAKER’S STRATEGY
≤
(5.2) 


1001|S0|
4000(|S0|− 2n
√log(n))


32k
≤ 1001|S0|1002
4000|S0|1001!32k
≤501
200032k
(5.3)
The second las inequali y holds because by inequali y (5.1), |S0| ≥ 2004n
√log(n),and
hus |S0|− 2n
√log(n)≥1001|S0|
1002 .
The p obabili y ha he e exis s a se o 2kou -edges such ha he endpoin s
o all emaining 32kou -edges om a e all in B∪Zis a mos
34k
2k!501
200032k
≤ 34ke
2k!2k501
200032k
(wi h 5.3)
≤(17e)2k501
200032k
= (17e)32k
16 501
200032k
≤3
232k501
200032k
=1503
400032k
Thus, he p obabili y ha he s a emen abo e is ue o all e ices in Zis a
mos
1503
400032k|Z|,
and he p obabili y ha he e exis Zand Bwi h he p ope ies men ioned abo e
is a mos
|Si|
|Z|! |S0|
|B|!1503
400032k|Z|
≤ |Si|e
|Z|!|Z| |S0|e
|B|!|B|1503
400032k|Z|
≤ |Si|e
|Z|!|Z| 2|S0|e
|S0|!|S0|
21503
400032k|Z|
≤ |Si|e
|Z|!|Z|(2e)2|Z|1503
400032k|Z|(since |Z| ≥ |S0|
4)
≤(2e)|Z|(2e)2|Z|1503
400032k|Z|
≤(2e)3|Z|1503
400032k|Z|
≤5·1503
4·400032k|Z|
64
5.4. VERIFYING MAKER’S STRATEGY
≤1
2|Z|(k≥1)
<2−n
√log(n)(since |Z| ≤ |S0|
4>n
√log(n))
= o 
n
qlog(n)
.
Case 2 : |Z| ≤ |S0|
4.
Conside a e ex ∈Sand an a bi a y se o 32k0-colo ed ou -edges inciden in
. No e ha hese edges ha e been chosen in case 1.1 o ei he s age. This choice
was made uni o mly a andom be ween all e ices w∈S0,such ha ( , w)was
unclaimed. Le u he B⊆S0 Zwi h |B|=j2k+1
30k−1|Z|k.Le A ,i ⊆S0be he se
o all e ices wsuch ha { , w}was unclaimed by ei he playe in u n i. Since
is no oublesome, a mos n
√log(n)B eake edges a e inciden in . Fu he mo e, a
mos 34k≤n
√log(n)Make -edges a e inciden in . This implies |A ,i| ≥ |S0|− 2n
√log(n).
|B∪Z|
|A|!32k
≤

|B|+|Z|
|S0|− 2n
√log(n)



32k
≤


32k
30k−1·|Z|
(|S0|− 2n
√log(n))


32k
≤ 32
29 ·1000 |Z|
999 |S0|!32k
.
The las inequali y holds, because by inequali y (5.1) |S0| ≥ 2000n
√log(n)and hus
|S0|− 2n
qlog(n)≥999
1000 |S0|.(5.4)
The e o e, he p obabili y ha he e exis s a se o 2kou -edges such ha he
endpoin s o all emaining 32kou -edges om all end in B∪Zis a mos
34k
2k! 32
29 ·1000 |Z|
999 |S0|!32k
≤ 34ke
2k!2k 32
29 ·1000 |Z|
999 |S0|!32k
= (17e)2k· 32
29 ·1000 |Z|
999 |S0|!32k
= (17e)1
16 ·32
29 ·1000 |Z|
999 |S0|!32k
< 3|Z|
2|S0|!32k
.
65
5.4. VERIFYING MAKER’S STRATEGY
So, he p obabili y ha he s a emen abo e is ue o all e ices in Zis a mos
3|Z|
2|S0|!32k|Z|,
and he p obabili y ha he e exis Zand Bwi h he p ope ies men ioned abo e
is a mos
|Si|
|Z|! |S0|
|B|! 3|Z|
2|S0|!32k|Z|
≤ |Si|e
|Z|!|Z| |S0|e
|B|!|B| 3|Z|
2|S0|!32k|Z|
≤ 1001 |S0|e
1000 |Z|!|Z| |S0|e(30k−1)
(2k+ 1) |Z|!2k+1
30k−1|Z| 3|Z|
2|S0|!32k|Z|(by de ini ion o B)
≤
1001e
1000 |S0|
|Z| e(30k−1)
2k+ 1 !2k+1
30k |S0|
|Z|!2k+1
30k−13
232k |Z|
|S0|!32k

|Z|
≤
1001e
1000 |S0|
|Z|(15e)2k+1
30k |S0|
|Z|!2k+1
30k−13
232k |Z|
|S0|!32k

|Z|
=
1001e
1000 (15e)2k+1
30k3
232k |S0|
|Z|!2k+1
30k−1|S0|
|Z| |Z|
|S0|!32k

|Z|
=
1001e
1000 (15e)2k+1
30k3
232k |Z|
|S0|!−2k+1
30k−1 |Z|
|S0|!−1 |Z|
|S0|!32k

|Z|
≤
1001e
1000 (15e)2k+1
30k3
232k |Z|
|S0|!30k

|Z|
.
Case 2.1 : |Z| ≥ √n, hen

1001e
1000 (15e)2k+1
30k3
232k |Z|
|S0|!30k

|Z|
≤ 1001e
1000 (15e)2k+1
30k3
232k1
430k!|Z|(since |Z| ≤ |S0|
4)
≤






1001e
1000 15e 332
232430 !k
| {z }
≤1
2







|Z|
≤2−|Z|≤2−√n= o n
log(n)!.
66
5.4. VERIFYING MAKER’S STRATEGY
Case 2.2 : |Z| ≤ √n. Recall ha by de ini ion |S0| ≥ n
√log(n), hus

1001e
1000 (15e)2k+1
30k3
232k |Z|
|S0|!30k

|Z|
≤
c√nqlog(n)
n

30k|Z|
( o some cons an c > 0)
≤
cqlog(n)
√n

30k|Z|
= o 
n
qlog(n)
.
Thus, he p oo is comple ed by summing o e all o hese p obabili ies.
Fo s≤j|Si|
2kde ine Asas he e en ha he e exis s a se Z⊆Sio size k ha
con ains no oublesome e ices and ha sa is ies N′(Z)≤|Si|
2−|Z|.We u he
de ine Bsas he e en ha he e exis s a se Z⊆Sio size s ha con ains no
oublesome e ices and ha sa is ies N′(Z)≤2k+1
30k−1|Z|.Now we ha e
|Si|
2
X
s=1
P(As∩Bs) = ⌈√n⌉
X
s=1
P(As∩Bs) +
|Si|
4
X
s=⌈√n⌉
P(As∩Bs) +
|Si|
2
X
s=|Si|
4
P(As∩Bs)
≤⌈√n⌉
X
s=1
P(Bs) +
|Si|
4
X
s=⌈√n⌉
P(Bs) +
|Si|
2
X
s=|Si|
4
P(As)
≤=⌈√n⌉
X
s=1
o
n
qlog(n)
+
|Si|
4
X
s=⌈√n⌉
o
n
qlog(n)
+
|Si|
2
X
s=|Si|
4
o
n
qlog(n)

≤|S |
2·o
n
qlog(n)
(since |Si| ≤ |S |)
≤1001(4k+ 3)3√k+ 2n
qlog(n)·o
n
qlog(n)
(by Co olla y 5.21)
= o (1) .
Thus wi h p obabili y 1−o (1) ,each se Z⊆Siwi h |Z| ≤ Si
2sa is ies |N′(Z)|>
|Si|
2−|Z|,o |N′(Z)| ≤ 2k+1
30k−1|Z|and he esul is p o ed.
Lemma 5.24 Wi h p obabili y 1−o (1) , o e e y i≥i∗in which case 1.2.2 applies
and o e e y Z⊆Siwhich con ains no oublesome e ex and o which |Z| ≤
√(k+2)n
√log(n)≤|S0|
1.000(4k+3)2,we ha e
N′(Z)>(4k+ 2)|Z|.
P oo . Le Z⊆Siwi h |Z| ≤ |S0|
1.000(4k+3)2such ha Zdoes no con ain any ou-
blesome e ices. Le u he B⊆S0 Zwi h |B|= (4k+ 2)|Z|.No e ha e e y
67
5.4. VERIFYING MAKER’S STRATEGY
ou -neighbo o such a non- oublesome e ex ∈Zwas chosen du ing case 1.1
du ing ei he s age. The neighbo s o non- oublesome e ices a e chosen uni o mly
a andom om all e ices in S0 ha a e no ye joined o . Le A⊆S0be he
se o e ices wsuch ha he edge { , w}was no claimed by nei he B eake no
Make . Since is non- oublesome B eake has chosen a mos n
√log(n)edges ha a e
inciden in . Fu he mo e, Make has chosen a mos 34k≤n
√log(n)edges inciden
in . This implies |A|≥|S0|− 2n
√log(n)
Now he p obabili y ha om a ixed e ex ha all i s 34kou -neighbo s a e
in Z∪Bis a mos
|B∪Z|
|A|!34k
≤

|B|+|Z|
|S0|− 2n
√log(n)



34k
=


(4k+ 3)|Z|
|S0|− 2n
√log(n)



34k
≤
(5.4) (4k+ 3)|Z|1000
|S0|999 !34k
So, he p obabili y ha e e y ou -neighbo o e e y e ex in Zend up in Z∪Bis
a mos
(4k+ 3)|Z|1000
|S0|999 !34k|Z|.
Thus, he p obabili y ha he e exis Zand Bas abo e is a mos
|Si|
|Z|! |S0|
|B|! (4k+ 3)|Z|1000
|S0|999 !34k|Z|
≤ |Si|e
|Z|!|Z| |S0|e
|B|!|B| (4k+ 3)|Z|1000
|S0|999 !34k|Z|
≤ 1001
1000 |S0|e
|Z|!|Z| |S0|e
|B|!|B| (4k+ 3)|Z|1000
|S0|999 !34k|Z|
= 1001
1000 |S0|e
|Z|!|Z| |S0|e
(4k+ 2)|Z|!(4k+2)|Z| (4k+ 3)|Z|1000
|S0|999 !34k|Z|
=
1001e
1000 e
(4k+ 2)!(4k+2) (4k+ 3)1000
999 !34k |Z|
|S0|!27k

|Z|
.
Now assume ha |Z| ≥ √n. Then we ha e

1001e
1000 e
(4k+ 2)!(4k+2) (4k+ 3)1000
999 !34k |Z|
|S0|!27k

|Z|
≤
1001e
1000 e
(4k+ 2)!(4k+2) (4k+ 3)1000
999 !34k 1
1.000(4k+ 3)2!27k

|Z|
≤ 1001
1000e(4k+3) 1000
999 34k1
1.00027k 1
(4k+ 3)20k(4k+ 2)(4k+2) !!|Z|
≤2−√n= o 
n
qlog(n)
.
68

5.4. VERIFYING MAKER’S STRATEGY
On he o he hand, i we assume ha |Z|<√n, hen he p obabili y ha he e
exis Zand Bas abo e is a mos

1001e
1000 e
(4k+ 2)!(4k+2) (4k+ 3)1000
999 !34k |Z|
|S0|!27k

|Z|
≤
cqlog(n)
√n

27k
( o some c > 0)
= o 
n
qlog(n)
.
Fo s∈[k]le Asbe he e en ha he e exis se s Zand Bas abo e swi h
|Z|=s. Then he p obabili y ha he e exis s a se s Zwi h |Z| ≤ √(k+2)n
√log(n)and
N′(Z)≤(4k+ 2)|Z|is a mos
P



[
s≤√(k+2)n
√log(n)
As



≤X
s≤√(k+2)n
√log(n)
P(As)(by he union bound)
=⌈√n⌉
X
s=1
P(As) + j√(k+2)n
√log(n)k
X
s=⌈√n⌉+1
P(As)
≤⌈√n⌉
X
s=1
o
n
qlog(n)
+j√(k+2)n
√log(n)k
X
s=⌈√n⌉+1
o
n
qlog(n)

≤q(k+ 2)n
qlog(n)·o
n
qlog(n)
= o (1) .
This p o es he lemma.
The nex esul allows us o ensu e ha o each i≥i∗,i case 1.2.2 applies, he
g aph induced by Siis connec ed, e en i up o 2kedges ha e been emo ed om
each e ex. The 2kedges ha a e emo ed in hese s eps ep esen he edges ha
o m he kHamil onian cycles ha migh al eady ha e been p o ec ed and can hus
no longe be used o o m o he Hamil on cycles.
Lemma 5.25 Fo e e y i≥i∗in which case 1.2.2 applies and o each Z⊆Si,
wi h |Z| ≤ |Si|
2 he se |N′(Z)|is non emp y wi h p obabili y 1−o (1) i no mo e
han 2kedges ha e been emo ed om each e ex. This implies Siis connec ed i
no mo e han 2kedges ha e been emo ed om each e ex and hus Siis (2k+ 1)-
edge-connec ed wi h p obabili y 1−o (1) .
Fu he mo e, i |Z| ≤ √(k+2)n
√log(n), hen |N′(Z)|>2k|Z|wi h p obabili y 1−o (1) .
69
5.4. VERIFYING MAKER’S STRATEGY
P oo . Le T⊂Zbe he se o oublesome e ices in Zand S:= Z T. Le
be a oublesome e ex. Since case 1.2.2 applies, 34kedges ha a e inciden in
we e added a e became oublesome. All o hese edges we e added in a s ep in
which case 2.1 o ei he s age applied. Whene e case 2.1 o ei he s age applies in
a ound ˆı, a oublesome e ex is connec ed o a e ex w∈V Sˆı.In addi ion
he e ex wis mo ed in o Sˆı+1.Thus wcanno be joined o ano he oublesome
e ex du ing a ound in which case 2.1 applies. This implies ha |N′(T)|con ains
a leas 34k|T| e ices.
|Z|+|N′(Z)| ≥ |T|+|N′(T)| ≥ 32k·|T|.
Now assume |Z|≤|Si|/2.So |S|≤|Z|≤|Si|/2.
Case 1 : |T|>2k+1
32k|Z|.This means we ha e a "la ge" numbe o oublesome
e ices in Z.
Then |Z|+|N′(Z)| ≥ 32k|T|>(2k+1)|Z|.This p o es he second s a emen o
he lemma. The i s s a emen can be ob ained by sub ac ing |Z| om bo h
sides o he inequali y, which yields |N′(Z)|>2k|Z|>0.Thus N′(Z)=∅.
Case 2 :|T| ≤ 2k+1
32k|Z|.We i s ha e
|S|=|Z|−|T|≥|Z|− 2k+ 1
32k|Z|=30k−1
32k|Z|.(5.5)
Then, since Sdoes no con ain any oublesome e ices and |S| ≤ |Si|/2as
pbse ed abo e, by Lemma 5.23 wi h p obabili y 1−o (1) we ge
|N′(S)|>2k+ 1
30k−1|S|o |N′(S)|>|Si|
2−|S|.(5.6)
using he assump ion |Z| ≤ |Si|/2.
This implies, using inequali y (5.5),
|Z|+|N′(Z)|≥|S|+|N′(S)|>2k+ 1
30k−1|S|+|S| ≥ 32k
30k−1|S| ≥ |Z|.
o
|Z|+|N′(Z)| ≥ |N′(S)|+|S|>|Si|
2≥ |Z|.
By sub ac ing |Z| om he le -hand-sides and he igh -hand-sides bo h in-
equali ies imply |N′(Z)|>0and hus N′(Z)=∅.
Fu he mo e, le us assume |Z| ≤ √(k+2)n
√log(n).Then |S| ≤ √(k+2)n
√log(n),and since S
does no con ain oublesome e ices, we can apply Lemma 5.24. So, wi h
p obabili y 1−o (1) we ha e |N′(S)|>(4k+ 1) |S|.Thus, wi h p obabili y
1−o (1) we ha e
|Z|+|N′(Z)| ≥|S|+|N′(S)|
>|S|+ (4k+ 1) |S|(by Lemma 5.24)
70
5.4. VERIFYING MAKER’S STRATEGY
≥(4k+ 2) |S|
≥(4k+ 2)30k−1
32k|Z|(wi h (5.5))
≥(2k+ 1) |Z|.
By sub ac ing |Z| om bo h sides o he inequali y we ge
|N′(Z)|>2k|Z|.
Theo em 5.26 Make can always make a choice as equi ed by he s a egy. Fu -
he mo e, he game does no end in Case 2 o any s age. Thus s age 1 ends in Case
1.2.2.
P oo . We i s show ha Make can make he equi ed choice in Case 1.1 o ei he
s age. In Case 1.1 o ei he s age Make is supposed o connec a non- oublesome
e ex in Si o a e ex in S0.Recall ha |S0|=1000(4k+3)2√(k+2)n
√log(n).Now i is a
non- oublesome e ex wi h d′
M( )<34k, hen we know ha Make chose a mos
34k0-colo ed ou -edges om , and a mos 2k(k+ 1)-colo ed edges inciden in
. Thus, he e a e a mos 36kMake ou -edges inciden in . Since kis cons an ,
clea ly 36k < n
√log(n).Fu he mo e, since is non- oublesome, by de ini ion B eake
chose a mos n
√log(n)edges inciden in . So,
d′
M( ) + dB( )≤36k+n
qlog(n)<2n
qlog(n).
Hence in bo h s ages Make can make he desi ed choice in Case 1.1, since a leas
|S0|− 2n
qlog(n)((4k+ 3)2q(k+ 2) −2) n
qlog(n)
e ices in S0a e no inciden in Make o B eake edges and a ailable o Make ’s
connec ions.
In case 1.2.1 o S age 2, Make is equi ed o connec an endpoin o a pa h
in P(l)
iwi h o a e ex in S0.No e ha is no in Siand hus non- oublesome.
The e o e, by he same a gumen s as we e used o he case 1.1, he e a e a leas
((4k+ 3)2q(k+ 2) −2) n
√log(b) e ices in S0 ha a e no ye adjacen o .
To handle case 2 in each o he s ages we combine Co olla y 5.21 wi h Lemma 5.22.
Make has o connec o some e ex in V Si−1.I case 2 applies in any s ep i,
he e exis s a oublesome e ex wi h d∗
Ml( )<34k. By Lemma 5.22, dB( )<
n−n(4k+3)3+2k+1
√log(n).Fu he mo e, Make claimed a mos 2kedges inciden in ha
we e chosen in Case 1.2.1 o s age 1. They we e (k+1)-colo ed in s ep i. In addi ion,
Make has chosen a mos 34k0-colo ed edges om be o e became oublesome
and a mos 34k−1 0-colo ed edges om a e became oublesome. Thus, he
71
5.4. VERIFYING MAKER’S STRATEGY
amoun o Make ou -edges inciden in is a mos 70k−1<70k. Since o all
i≤ , Si⊆S ,Co olla y 5.21 pa 1 yields
|Si|≤|S |<((4k+ 3)2q(k+ 2)1001)n
qlog(n).
So le A ⊆V Si−1be he se o e ices ha can be chosen o be connec ed o
by Make in s ep i. Then
|A | ≥ n−|Si|−dB( )−70k
≥n−((4k+ 3)2q(k+ 2)1001)n
qlog(n)−(n−n1000(4k+ 3)3+ 2k+ 1
qlog(n))−70k
≥n((4k+ 3)31000 −((4k+ 3)2q(k+ 2)1001))
qlog(n)−70k > 0,
as kis cons an .
Thus Make can always choose an edge in Case 2.1 and he game does no end in
Case 2.2. o ei he s ep.
The idea o using o a ions o build Hamil onian cycles was i s in oduced by
Posa [Pó76]. His echnique uses he ollowing ac . Le P= 0 1. . . xbe a pa h o
leng h x≥4and y≤x−2such ha { x, y} ∈ E. Then P+{ x, y}−{ y, y+1}
is a pa h o leng h xand endpoin s y+1 and . Howe e , he ype o o a ions ha
a e help ul in ou con ex is limi ed.
De ini ion 5.27 Le P= 1. . . xbe a pa h wi h bo h endpoin s in S′
i,and
y≤x−2such ha { x, y} ∈ Mlwi h x∈e. Then we call P′=P+
{ x, y}−{ y, y+1}a limi ed -Ml- o a ion om P. We call a pa h P′′ cons uc ible
om Pby epea ed limi ed -Ml- o a ions om P, i he e exis s a se ies o limi ed
-Ml- o a ions P,...,P′′, such ha he end- esul is P′′.
y
x−1
x
Figu e 5.5: He e we depic a limi ed -Ml- o a ion wi h he same no a ion as in
De ini ion 5.27, ob aining P′ om P.
This echnique allows us o cons uc a amily o pa hs wi h he same e ex se
and leng h as P(l)
i.By showing ha his amily is la ge we will p o e ha Make
will always be able o close a cycle on he e ices o P(l)
i.We begin by showing ha
a leas one o hese pa hs has bo h o i s endpoin s in S′
i.
72
5.6. ANALYZING THE DURATION OF STAGE 3
Case 1.2.2: I he e exis s a ∈Ai−1,bu no w∈Ai−1such ha Case
1.2.1 would be sa is ied, choose w′∈S0,such ha { , w′} /∈M∪B.
Then add { , w},se c({ , w}) = k, Ci=Ci−1, Ai=Ai−1 { }and
Bi=Bi−1∪{ }.
Case 1.2.3: O he wise Ai−1=∅and we end he game.
Case 2: The e is a oublesome e ex w∈Ci−1such ha d∗
M( )<34k.
Selec o be a oublesome e ex ∈Ci−1such ha d∗
M( )<34k, ha ing
maximum dange dang( ) := dB( )−bd∗
M( )(wi h ies a bi a ily b oken ).
Then
Case 2.1: I he e is no w′∈V−Ci−1such ha ( , w′)is no in B∪M,
end he game.
Case 2.2: O he wise,
–choose such a w′and add ( , w′) o M. Colo ( , w′)wi h colo 0,so
c( , w∗) = 0.
–Se Ci=Ci−1∪{w′}and o each j∈[k]se Pj
i o be he se ob ained
om Pj
i−1by dele ing he pa h P ha con ained w′and adding he
componen s o P−w′.
5.6 Analyzing he du a ion o S age 3
To analyze he addi ional s age o he algo i hm we ecall he ollowing de ini ions.
is he numbe o u ns ca ied ou in S age 1 and S age 2, and is he numbe o
oublesome e ices a he end o he game. Fu he , le 2be he numbe o u ns
played in S age 1, S age 2 and S age 3.
By Theo em 5.7 a mos k∗n+On
√log(n)=(k−1)n
2 u ns ha e been ca ied ou .
We now es ima e he numbe o u ns ha we e ca ied ou in S age 3.
Lemma 5.33 The numbe o u ns in which Case 2 o ei he S age applies can be
es ima ed o be a mos 34 ·k∗· .
P oo . The p oo is analogous o he p oo o Lemma 5.11.
Whene e Case 2 applies in any s ep o ei he s age, edges a e added o a ou-
blesome e ex wi h d∗
M( )<34k∗.We add one edge pe u n, hus, he numbe
o u ns spen on each oublesome e ex is 34k∗.Since he e a e oublesome
e ices a he end o he algo i hm, he numbe o ounds spen in hese cases is a
mos 34k∗ .
Lemma 5.34 The numbe o u ns aken in Case 1.1 o ei he S age applies can be
es ima ed o be a mos 34 ·k∗·|C 2|.
P oo . The p oo is analogous o he p oo o Lemma 5.12.
Whene e Case 1.1 o ei he s age e e y oublesome e ex sa is ies d∗
M( ) =
34k. No e ha o each i1≤ , Si1⊆S =C0.Fu he mo e, o each i2≤ 2we
ha e Ci2⊆C 2.Thus, o each non- oublesome e ex ∈C 2we inc ease d′
M( )
79

5.6. ANALYZING THE DURATION OF STAGE 3
o 34k, adding one edge pe u n. In he wo s case all e ices in C 2a e non-
oublesome and ha e o be inc eased in hese s eps. Thus, he numbe o u ns is
a mos 34k·|C 2|.
Lemma 5.35 The numbe o u ns in which Case 1.2.1 o S age 3 applies, can be
es ima ed o be a mos |A0|
2≤n
2.
P oo . Since A0⊆V, we ha e |A0|≤|V| ≤ n. I Case 1.2.1 o S age 3 applies, he e
is a pai o e ices , w ∈Ai−1⊆A0in di e en pa h componen s o P(k∗)
.
Since bo h , w a e hen emo ed om |Ai−1|,i akes a mos |A0|
2≤n
2such
s eps o emo e e e y e ex om A0.
Lemma 5.36 The numbe o u ns in which Case 1.2.1 o S age 3 applies can be
es ima ed o be a mos 2n
√log(n).
P oo . We show ha o each i≤ 2so ha in s ep iCase 1.2.1 o S age 3 applies,
we ha e |Ai−1|<2n
√log(n).Whene e Case 1.2.1 o S age 3 applies, Make educes he
size o Ai−1by one. So a mos 2n
√log(n)such s eps a e needed un il Ai−1is emp y.
I Case 1.2.2 o S age 3 is ca ied ou , Case 1.2.1 o S age 3 does no apply. Thus,
he e exis s no pai o e ices , w ∈Ai−1,such ha [ ](k∗)
= [w](k∗)
and { , w}is
unclaimed. Now conside an a bi a y ∈Ai−1.Since he e is no w∈Ai−1such
ha [ ](k∗)
= [w](k∗)
and { , w}is unclaimed, each w∈Ai−1 { }mus ul ill one o
he ollowing wo p ope ies. Ei he wis in [ ](k∗)
,o { , w}has been claimed by a
playe .
Thus
|Ai| ≤ dB( ) + dM( ) + |[ ](k∗)
|.
Obse e ha |[ ](k∗)
| ≤ 2 log(n)<n
2√log(n)by Rema k 5.10.
Now we bound he numbe o w∈Ai−1 { }such ha { , w}has been claimed
by a playe . Since is in Ai−1,i is no in Ci−1and is non- oublesome, so by
de ini ion dB( )<n
√log(n).Fu he mo e, since is an in e io e ex o [ ](j)
o any
j∈[k∗],exac ly 2k∗Make edges inciden in ha e been added. As k∗is cons an
and nis assumed o be la ge enough, dM( )=2k∗≤n
2√log(n).
We conclude
|Ai| ≤ dB( ) + dM( ) + |[ ](k∗)
| ≤ n
qlog(n).
We now can gi e a p elimina y uppe bound on he numbe o u ns ha a e
ca ied ou du ing S ages 1, 2 and 3. No e ha we coun he numbe o u ns ca ied
ou in case 2 and case 1.1 double. This will u n ou o be no p oblema ic, because
he numbe o s eps ca ied ou in hese s eps is On
√log(n).
80
5.6. ANALYZING THE DURATION OF STAGE 3
Lemma 5.37 The numbe o u ns ca ied ou in S ages 1, 2 and 3 in o al is a
mos
(2k∗+ 1)n
2+ 34k∗· + 34k∗·|C 2|+O
n
qlog(n)
≤70k∗·n.
P oo . This esul is analogous o he p oo o Lemma 5.16.
By he lemma a 5.33 h ough 5.36 and Lemma 5.20 he numbe o mo es played in
S ages 1, 2 and 3 combined is a mos
34k∗·
| {z }
Lemma 5.33
+ 34k∗·|C 2|
| {z }
Lemma 5.34
+n
2
|{z}
Lemma 5.35
+2n
qlog(n)
| {z }
Lemma 5.36
+ 2k∗n+O
n
qlog(n)

| {z }
Lemma 5.20
=(2k∗+ 1)n
2+ 34k∗· + 34k∗·|C 2|
| {z }
≤68k∗n
+O
n
qlog(n)

≤70k∗·n,
using he i ial uppe bound n o |C 2|and .
Lemma 5.38 The numbe o oublesome e ices a e S ages 1, 2 and 3 a e com-
ple ed is a mos
≤140k∗n
qlog(n).
P oo . This p oo is analogous o he p oo o Lemma 5.17.
By Lemma 5.37 he game las s o a mos 70k∗n u ns. Since B eake claims
b≤n
log(n)edges in each u n, we ha e
|B| ≤ 70 ·k∗·n·b≤70k∗n2
log(n).
Fu he mo e, each oublesome e ex has B eake deg ee a leas n
√log(n).In addi-
ion each B eake edge is inciden in a mos wo oublesome e ices. Thus
≤2·|B|· qlog(n)
n≤2·70 ·k∗n
qlog(n).
Lemma 5.39 A he end o he game we ha e
|C 2| ≤|S0|+ 35k∗
≤1000(4k∗+ 3)2√k∗+ 2n
qlog(n)+ 35k∗
≤1000(4k∗+ 3)2√k∗+ 2n
qlog(n)+ 4900k∗n
qlog(n).
81
5.6. ANALYZING THE DURATION OF STAGE 3
P oo . This p oo is analogous o he p oo o Lemma 5.18.
I a he end o S age 3 a e ex is in C 2,i a i ed he e by one o he
ollowing h ee ways: a) i was in S0,b) i became oublesome o e he cause o
he game (which implies i was added be ween s eps) and c) i is one o he 34k∗
ou -neighbo s o a oublesome e ex du ing case 1.1. o ei he S age. Thus o
each oublesome e ex a mos 35k∗ e ices end up in C 2,and a mos 35k∗
e ices sa is y possibili y b) o c). Ob iously, he e a e |S0| e ices which sa is y
possibili y a).
The second inequali y ollows om he de ini ion o S0and he hi d inequali y
is ue by Lemma 5.38.
Now ha we ha e gi en a ough uppe bound on he numbe o ounds played,
i is ime o e ine ou esul wi h he new uppe bounds o and |C 2|.
Lemma 5.40 A mos kn
2+On
√log(n) u ns ha e been ca ied ou in S ages 1, 2
and 3.
P oo . By Lemma 5.37 he game ends a e
(2k∗+ 1)n
2+ 34k∗· + 34k∗·|C 2|+O
n
qlog(n)

u ns. By Lemma 5.38, ∈ On
√log(n)and by Lemma 5.39, |C 2| ∈ On
√log(n).
Thus, he numbe o u ns ha we e ca ied ou by Make is a mos
(2k∗+ 1)n
2+O
n
qlog(n)
=k·n
2+O
n
qlog(n)
.
Since he game las s o a mos k·n
2+On
√log(n) u ns and B eake claims
b≤n
log(n)edges in each u n,
|B| ≤ 
k·n
2+O
n
qlog(n)

·b≤(k+ 1)n2
2 log(n).
Each oublesome e ex has B eake deg ee a leas n
√log(n).In addi ion, each
B eake edge is inciden in a mos wo oublesome e ices. Thus
≤2·|B|· qlog(n)
n≤2·k+ 1
2
n
qlog(n)≤(k+ 1) ·n
qlog(n).
Co olla y 5.41 A he end o he game we ha e
≤(k+ 1) n
qlog(n)and |C 2|≤|S0|+ 35(k+ 1)k∗qlog(n).
82
5.7. PROVING THE k-EDGE-CONNECTIVITY OF MAKER’S GRAPH
P oo . Each oublesome e ex has B eake deg ee a leas n
√log(n).In addi ion each
B eake edge is inciden in a mos wo oublesome e ices. Thus
≤2·|B|· qlog(n)
n≤2·k+ 1
2
n
qlog(n)≤(k+ 1) ·n
qlog(n).
By Lemma 5.39 we ha e
|C 2|≤|S0|+ 35k∗ ≤ |S0|+ 35(k+ 1)k∗qlog(n).
5.7 P o ing he k-Edge-Connec i i y o Make ’s
G aph
We al eady es ablished ha he game ends a e a mos kn
2+On
√log(n) u ns.
We now ha e o show ha he Make g aph is k-edge connec ed a e s ages 1, 2 and
3 ha e been ca ied ou . We begin by showing ha he algo i hm is well-de ined,
i.e. ha he choices ha i equi es can be made in any gi en s ep. O cou se, his
is ue o e e y s ep du ing s ages 1 and 2. Thus we will only conside he s eps
aken du ing S age 3.
Lemma 5.42 Make can always make he mo es equi ed by he algo i hm k-edge-
connec i i y (du ing S ep 3).
P oo . We conside he cases o S age 3.
We i s obse e ha Make can make he mo e equi ed by he algo i hm when
Case 1.2.1 applies, since his case applies only when he edge Make is supposed o
choose exis s and is unclaimed.
The a gumen s ha Make can make he equi ed choice in Case 1.1 and Case
1.2.2 a e simila and can be handled oge he . In bo h o hese cases Make has o
connec a non- oublesome e ex o a e ex w∈S0.No e ha in Case 1.1 is
explici ly non- oublesome, while in Case 1.2.2 is in Ai−1.Since all oublesome
e ices in s ep ia e in Ci, is non- oublesome when Case 1.2.2 applies. Thus,
dB( )≤n
√log(n).Fu he mo e, Case 1.1 equi es d′
M( )<34k < n
√log(n)and Case
1.2.2 applies o a e ex o Ai−1.So, i Case 1.2.2 applies, is an in e io e ex
o [ ](j)
o each j∈[k∗].These e ices a e no inciden in Make edges wi h an
endpoin in Ci−1⊇S0by cons uc ion. Thus, he e exis a leas |S0| − dB( )−
d′
M( )≥ |S0|− 2n
√log(n) e ices w∗∈S0such ha ( , w∗)is unclaimed i Case 1.1 o
Case 1.2.2 o S age 3 apply.
Now we wan o show ha Make can make he equi ed choice in Case 2 o S age
3. So, le i≤ 2such ha Case 2 o S age 3 applies. Le ∈Ci−1be a oublesome
e ex wi h d∗
M( )≤34k∗and maximum dange . By Lemma 5.22, dB( )≤n−
(4k+3)3n+2k+1
√log(n).Fu he mo e, was non- oublesome when S age 3 s a ed, o he wise
83
5.7. PROVING THE k-EDGE-CONNECTIVITY OF MAKER’S GRAPH
S age 2 would no ha e concluded. The numbe o edges p esen in a he s a
o S age 3 ha end in V C and we e o some colo j∈[k∗]when was mo ed o
C is a mos 2k∗≤n
√log(n).In conclusion, he e exis a leas
|V Ci−1|−2k∗−dB( )
≥|V|−|Ci−1|−2k∗−dB( )
≥n−|C 2|− n
qlog(n)−n+(4k+ 3)3n+ 2k+ 1
qlog(n)
≥(4k+ 3)3n2k+ 1
qlog(n)−n
qlog(n)−|C 2|(by Co olla y 5.41)
e ices w∗∈V Ci−1such ha { , w∗}is unclaimed.
P oo o Theo em 5.9. I kis e en Make builds k∗=⌊k
2⌋Hamil on cycles wi h he
algo i hm Hamil on-Cycles. By Menge ’s heo em he cons uc ed g aph is k-edge-
connec ed and we a e done.
So, le k∈N≥3be odd. No e ha 2k∗+ 1 = k. Now, by Lemma 5.25 and since
2k∗+ 1 = k, C0is k-edge connec ed wi h p obabili y 1−o (1) .
We assume o a momen ha he e exis s a se ˆ
Eo k−1edges such ha M ˆ
E
is no connec ed. Then he e exis s ∈Vno belonging o he same (M ˆ
E)-
componen as C0.
Since o each colo j∈[k] he e exis wo j-colo ed pa hs in Mconnec ing
and C0,ˆ
Ehas o con ain wo edges o each colo om Mand bo h ha e o be in
[ ](k∗)
.O he wise, he e is a pa h emaining om o some e ex o C0.
C0
Figu e 5.11: An example o a si ua ion whe e is an inne e ex o a ed-colo ed
pa h and a blue-colo ed pa h i.e. k∗= 2, implying 4=2k∗edges ( wo ed, wo
blue) ha e o be emo ed o disconnec om C0.
84

5.8. CONCLUSION AND OPEN QUESTIONS
I is in V C0,i has o be in B 2,since a he end o he game A 2is emp y.
I ends up o be in B , he e a e wo cases.
Case 1: The e exis s a w∈S0⊆C0such ha { , w} ∈ Mand c({ , w}) = k
and his edge was added in Case 1.2.2 o S age 3. Since c({ , w}) = k, and all edges
in ˆ
Ea e colo ed wi h a colo in [k∗],{ , w}/∈ˆ
E. Thus, is in he same (M ˆ
E)-
componen as C0,which is a con adic ion o he assump ion ha and C0a e in
di e en (M ˆ
E)-componen s.
Case 2: The e exis s a w∈Bwi h [ ](k∗)
= [ ](k∗)
such ha { , w} ∈ Mand
c({ , w}) = k. Since ˆ
Econ ains only wo k∗-colo ed edges, bo h o which connec
e ices in [ ](k∗)
,no edges ha e been emo ed om [w](k∗)
.So, in M ˆ
E, he e
exis s an edge om S0 o an endpoin uo [w](k∗)
,which was chosen in Case 1.2.1
o S age 2. Then he e exis s a sub-pa h o [w](k∗)
connec ing u o wand inally he
edge { , w}in M ˆ
E. Because S0⊆C0, is in he same (M ˆ
E)-componen as
C0.This is again a con adic ion o he assump ion ha and C0a e in di e en
(M ˆ
E)-componen s.
This concludes he p oo .
5.8 Conclusion and Open Ques ions
In his chap e we managed o gene alize an app oach o B üs le e al. [BCN+23]
o show ha o each k≥2Make can win he 1 : n
log(n)−Cn
log(n)3/2Make -B eake
k-edge-connec i i y game in a mos k
2n+ o (n) u ns. This is also he op imal
numbe o ounds up o he o (n) e m and imp o es he o me ly known bound by
a ac o o mo e han 8.We also used his s a egy o show ha Make wins he
1 : n
log(n)−Cn
log(n)3/2Make -B eake k- ac o game in lk
2mn+ o (n) ounds o each
k≥2.Since Make needs a leas k
2n ounds o win he k- ac o game, he only
possibili y o imp o e his esul up o he o (n) e m is o educe he numbe o
u ns by n
2i kis odd. We pose he ollowing na u al ques ions:
Ques ion 1 : Can he app oach desc ibed in his chap e be used o show
ha Make wins he 1 : n
log(n)−Cn
log(n)3/2k- e ex-connec i i y game in a mos
k
2n+ o (n) u ns?
Ques ion 2 : Is i possible o modi y he app oach in such a way ha i yields
a Make win in he 1 : n
log(n)−Cn
log(n)3/2k- ac o game using a mos k
2n+ o (n)i
kis odd?
85
Bibliog aphy
[AKS99] Noga Alon, Michael K i ele ich, and Benny Sudako . Colo ing G aphs
wi h Spa se Neighbo hoods. Jou nal o Combina o ial Theo y, Se ies
B, 77(1):73–82, 1999.
[Alo92] Noga Alon. Choice Numbe s o G aphs: a P obabilis ic App oach.
Combina o ics, P obabili y and Compu ing, 1(2):107–114, June 1992.
[Alo93] Noga Alon. Res ic ed colo ings o g aphs. In K. Walke , edi o , Su -
eys in Combina o ics, 1993, pages 1–34. Camb idge Uni e si y P ess,
1. edi ion, July 1993.
[AS10] Noga Alon and Benny Sudako . Inc easing he ch oma ic numbe o a
andom g aph. Jou nal o Combina o ics, 1(4):345–356, 2010.
[BCN+23] Noah B üs le, Sa ah Clusiau, Vishnu V. Na ayan, Ndiamé Ndiaye,
B uce Reed, and Ben Seamone. The speed and h eshold o he bi-
ased pe ec ma ching and Hamil on cycle games. Disc e e Applied
Ma hema ics, 332:23–40, June 2023.
[BE76] B. Bollobas and P. E dös. Cliques in andom g aphs. Ma hema i-
cal P oceedings o he Camb idge Philosophical Socie y, 80(3):419–427,
No embe 1976.
[BFM03] Tom Bohman, Alan F ieze, and Ryan Ma in. How many andom edges
make a dense g aph hamil onian? Random S uc u es & Algo i hms,
22(1):33–42, 2003.
[BMPP20] Julia Bö che , Richa d Mon gome y, Ola Pa czyk, and Yu y Pe son.
EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RAN-
DOMLY PERTURBED GRAPHS. Ma hema ika, 66(2):422–447, Ap il
2020.
[Bol85] Béla Bollobás. Random g aphs. Academic P es, London, 1985.
[Bol88] Béla Bollobás. The ch oma ic numbe o andom g aphs. Combina o -
ica, (8), 1988.
[Bol98] Béla Bollobás. Mode n G aph Theo y, olume 184 o G adua e Tex s
in Ma hema ics. Sp inge New Yo k, New Yo k, NY, 1998.
86
BIBLIOGRAPHY
[BPSS23] Julia Bö che , Ola Pa czyk, Amedeo Sgueglia, and Joze Skokan. T i-
angles in andomly pe u bed g aphs. Combina o ics, P obabili y and
Compu ing, 32(1):91–121, Janua y 2023.
[CE78] V. Ch á al and P. E dös. Biased Posi ional Games. In Annals o
Disc e e Ma hema ics, olume 2, pages 221–229. Else ie , 1978.
[CHMP20] Dennis Clemens, Fabian Hamann, Yannick Mogge, and Ola Pa czyk.
Posi ional games on andomly pe u bed g aphs. a Xi :2009.14583
[ma h], Sep embe 2020. a Xi : 2009.14583.
[Die17] Reinha d Dies el. G aph Theo y, olume 173 o G adua e Tex s in
Ma hema ics. Sp inge , Be lin, Heidelbe g, i h edi ion edi ion, 2017.
[DMT19] Shagnik Das, Pa ick Mo is, and And ew T eglown. Ve ex Ramsey
p ope ies o andomly pe u bed g aphs. a Xi :1910.00136 [ma h],
Sep embe 2019. a Xi : 1910.00136.
[DRRS20] And zej Dudek, Ch is ian Reihe , And zej Ruciński, and Ma hias
Schach . Powe s o Hamil onian cycles in andomly augmen ed g aphs.
Random S uc u es & Algo i hms, 56(1):122–141, Janua y 2020.
[ER59] P. E dős and A. Rényi. On Random G aphs. Publica iones Ma hema -
icae, 6:pp 290–297, 1959.
[ERT79] P. E dős, A. L. Rubin, and H. Taylo . Choosabili y in g aphs. P oc.
Wes Coas Con . on Combina o ics, G aph Theo y and Compu ing,
Cong essus Nume an ium, XXVI:125–157, 1979.
[FK16] Alan F ieze and Michał Ka oński. In oduc ion o andom g aphs. Cam-
b idge Uni e si y P ess, Camb idge, 2016.
[Gil59] E. N. Gilbe . Random G aphs. The Annals o Ma hema ical S a is ics,
30(4):1141–1144, Decembe 1959.
[GS09] Heidi Gebaue and Tibo Szabó. Asymp o ic andom g aph in ui ion
o he biased connec i i y game. Random S uc u es & Algo i hms,
35(4):431–443, Decembe 2009.
[HKSS14] Dan He e z, Michael K i ele ich, Miloš S ojako ić, and Tibo Szabó.
Posi ional Games, olume 44 o Obe wol ach Semina s. Sp inge Basel,
Basel, 2014.
[HR21] Annika Heckel and Oli e Rio dan. How does he ch oma ic numbe
o a andom g aph a y? 2021. Publishe : a Xi Ve sion Numbe : 2.
[K i00] Michael K i ele ich. The Choice Numbe o Dense Random G aphs.
Combina o ics, P obabili y and Compu ing, 9(1):19–26, Janua y 2000.
[K i10] Michael K i ele ich. The c i ical bias o he Hamil onici y game
is (1+o(1))n/ln(n). Jou nal o he Ame ican Ma hema ical Socie y,
24(1):125–131, Augus 2010.
87
BIBLIOGRAPHY
[KS VW03] Michael K i ele ich, Benny Sudako , H. an Vu, and Nicholas C.
Wo mald. On he p obabili y o independen se s in andom g aphs.
Random S uc u es and Algo i hms, 22(1):1–14, 2003.
[Ma 70] D. Ma ula. The la ges clique size in a andom g aph. Sou he n
Me hodis Uni e si y. P oc. o he Second Chapel Hill Con e ence on
Combina o ial Ma hema ics and I s Applica ions, pages 356–369, 1970.
[McD89] Colin McDia mid. On he me hod o bounded di e ences. In
J. Siemons, edi o , Su eys in Combina o ics, 1989, pages 148–188.
Camb idge Uni e si y P ess, 1. edi ion, Augus 1989.
[Men27] Ka l Menge . Zu allgemeinen Ku en heo ie. Fundamen a Ma hema -
icae, 10:96–115, 1927.
[Pó76] L. Pósa. Hamil onian ci cui s in andom g aphs. Disc e e Ma hema ics,
14(4):359–364, 1976.
[SS87] Eli Shami and Joel Spence . Sha p concen a ion o he ch oma ic
numbe on andom g aphs Gnp. Combina o ica, 7(1):121–129, Ma ch
1987.
[Łu91] Tomasz Łuczak. The ch oma ic numbe o andom g aphs. Combina-
o ica, 11(1):45–54, Ma ch 1991.
88