Colorings of Randomly Augmented Graphs and a Maker-Strategy for the k-Edge-Connectivity Game
Abstract
In this thesis the behavior of two graph properties on randomly augmented graphs are studied, as well as multiple Maker-Breaker games. It contains tight upper bounds for the chromatic number and the choice number of randomly augmented graphs. Furthermore it gives an upper bound for the number of turns it takes Maker to win several Maker-Breaker games.
Full text
Colorings of Randomly Augmented Graphs and a Maker-Strategy for the k-Edge-Connectivity Game Dissertation zur Erlangung des Doktorgrades der Mathematisch-Naturwissenschaftlichen Fakultät der Christian-Albrechts-Universität zu Kiel vorgelegt von Jan Erhard Geest Kiel, 2024 unter der Betreuung von Prof. Dr. Anand Srivastav
Erster Gutachter : Prof. Dr. Anand Srivastav Zweiter Gutachter : Prof. Dr. Sören Christensen Datum der mündlichen Prüfung : 03. September 2024
Danksagungen An dieser Stelle möchte ich einigen Personen danken, ohne die ich diese Arbeit nicht in dieser Form hätte fertigstellen können. An erster Stelle bedanke ich mich bei Prof. Dr. Srivastav für die Betreuung und Beratung während meiner Forschungsarbeit. Weiterhin bedanke ich mich bei allen Mitgliedern der Arbeitsgruppe Diskrete Optimierung der Christian-Albrechts-Universität zu Kiel, deren hilfreiche Anmerkungen mir sehr geholfen haben und die mir in unseren Gesprächen in den Oberseminaren ermöglichten, gute Ideen zu finden und schlechte Ideen als solche zu erkennen und zu verwerfen. Darüber hinaus bedanke ich mich bei meinen Eltern und meiner Familie, deren emotionale und finanzielle Unterstützung es mir ermöglicht hat, stets mit vollem Einsatz zu forschen. Gillian Krüger danke ich für ihre unermüdlichen Ermutigungen und ihr stets offenes Ohr. 2
Contents 1 Introduction 7 1.1 On the model of Randomly Augmented Graphs . . . . . . . . . . . . 7 1.2 On the Chromatic Number of Random Graphs . . . . . . . . . . . . . 8 1.3 On the Choice Number of Random Graphs . . . . . . . . . . . . . . . 9 1.4 On Maker-Breaker Games . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Material and Methods 11 2.1 On the Chromatic Number of Random Graphs . . . . . . . . . . . . . 11 2.2 On the Choice Number of Random Graphs . . . . . . . . . . . . . . . 22 2.3 Winning the k-edge-Connectivity Game using Krivelevich’s techniques 23 3 On the Chromatic Number of Randomly Augmented Graphs 28 3.1 Introduction................................ 28 3.1.1 Previouswork........................... 28 3.1.2 Ourresults ............................ 29 3.2 Bounding the chromatic number of pertH,p ............... 30 3.2.1 The Case p∈(0,1) isconstant.................. 30 3.2.2 The Case p(n) = n−θfor some θ∈0,1 3............ 33 3.3 Tightness of upper bounds for certain graphs . . . . . . . . . . . . . . 36 3.4 Coloring Augmented Graphs with Host Graphs of small Chromatic Number .................................. 37 3.5 Conclusion................................. 42 4 On the Choice Number of Randomly Augmented Graphs 44 4.1 Introduction................................ 44 4.1.1 PreviousResults ......................... 44 4.1.2 OurResult ............................ 45 4.2 Bounding the Choice Number of Randomly Augmented Graphs . . . 45 4.3 Remarksontightness........................... 49 4.4 Conclusion................................. 50 5 An Algorithm to win the biased k-Edge-Connectivity and k-Factor Games fast 51 5.1 Introduction................................ 51 5.1.1 Previouswork........................... 51 5.1.2 Ourresults ............................ 52 5.1.3 Methods and Innovations . . . . . . . . . . . . . . . . . . . . . 53 3
CONTENTS 5.2 Describing the Algorithm Hamilton-Cycles ............... 53 5.2.1 Stage 1: Creating a Graph consisting of an Expander and few paths................................ 54 5.2.2 Stage 2: Closing kHamilton Cycles . . . . . . . . . . . . . . . 55 5.3 Bounding the Number of Rounds played . . . . . . . . . . . . . . . . 57 5.4 Verifying Maker’s Strategy . . . . . . . . . . . . . . . . . . . . . . . . 62 5.5 Describing the algorithm used to prove k-Edge Connectivity . . . . . 77 5.5.1 Stage 3: Bonus Stage for odd k................. 78 5.6 Analyzing the duration of Stage 3 . . . . . . . . . . . . . . . . . . . . 79 5.7 Proving the k-Edge-Connectivity of Maker’s Graph . . . . . . . . . . 83 5.8 Conclusion and Open Questions . . . . . . . . . . . . . . . . . . . . . 85 4
Summary In this thesis we study the behavior of two graph properties on randomly augmented graphs as well as multiple Maker-Breaker games. We prove tight upper bounds for the chromatic number and the choice number of randomly augmented graphs and give an upper bound for the number of turns it takes Maker to win several MakerBreaker games. In Chapter 2 we give slightly improved probability bounds for the values of the chromatic number of and the choice number for the Gn,p random graph model using techniques used by Bollobás [Bol88] and Kahn [Alo93] respectively, combining them with a result by Krivelevich et al. [KSvVW03], as this allows for improved results in Chapter 3 and Chapter 4. We also calculate an explicit bound for the number of turns Maker needs to win the biased k-edge-connectivity game, using well-known strategies, as such results did not give explicit upper bounds for the number of turns but rather focused on identifying certain games as Maker wins. In Chapter 3 we show that for randomly augmented graphs pertH,p the chromatic number χpertH,pfor each ε > 0is bounded from above by χpertH,p≤(1 + ε)nlog(b) 2(log(n)−log(χ(H))) a.a.s. (1) where b= 1/(1−p)as long as p∈(0,1) is constant and χ(H)∈o (n).We also show that inequality 1 holds, if p=p(n) = n−θfor some θ∈(0,1/3) and χ(H)≤n1−3θ. Since the proof is non-constructive we also give slightly less powerful constructive proofs. In Chapter 4 we show that the upper bound established in Chapter 3 for the chromatic number of a randomly augmented graph also holds for the choice number of the randomly augmented graph, i.e. for each ε > 0 χlpertH,p≤(1 + ε)nlog(b) 2(log(n)−log(χ(H))) a.a.s. (2) where b= 1/(1 −p)as long as p∈(0,1) is constant and χ(H)≤n−θfor some θ∈(0,1/2). In Chapter 5 we prove that Maker can win the biased Maker-Breaker k-HamiltonCycle game in at most kn + o (n)rounds. We use this result to show that Maker can win the k-edge-connectivity game in at most k 2n+ o (n)turns and that Maker can win the k-factor game in at most lk 2mn+ o (n)for each k∈N≥2.In the case of the k-edge-connectivity game this bound on the number of turns is optimal up to the o (n)term. The bound in the k-factor game is optimal for even k, while for odd ka lower bound of k 2ncould be possible. For each of these three games the bound was improved by a factor of at least 8. We achieve these results by building an expander-like structure on a set of θn √log(n)vertices and families of differently colored paths which will form the basis for the Hamilton cycles we build, before we start closing the Hamilton cycles. This approach is a generalization of an approach introduced by Brüstle et al. [BCN+23] that showed that Maker can win the biased Hamiltonicity game in at most n+ o (n)moves. 5
Zusammenfassung In dieser Arbeit untersuchen wir das Verhalten von zwei Eigenschaften zufällig augmentierter Graphen sowie mehrere Maker-Breaker Spiele. Wir beweisen scharfe obere Schranken für die chromatische Zahl und die listenchromatische Zahl zufällig augmentierter Graphen und geben verschiedene obere Schranken für die Anzahl der Züge, in denen Maker gewisse biased Maker-Breaker Spiele gewinnen kann. In Kapitel 2 geben wir leicht verbesserte Wahrscheinlichkeitsschranken für die Werte der chromatischen Zahl und der listenchromatischen Zahl des Gn,p Zufallsgraphen. Hierfür verwenden wir Techniken von Bollobás [Bol88] bzw. Kahn [Alo93] und kombinieren diese mit einem Resultat von Krivelevich et al. [KSvVW03], da dies eine Verbesserung unserer Ergebnisse in den Kapiteln 3 und 4 ermöglicht. Des Weiteren berechnen wir explizit die beste bisher bekannte obere Schranke für die Anzahl der Züge, die Maker benötigt, um das k-Kantenzusammenhangsspiel zu gewinnen. Die existierenden Ergebnisse ließen diese Information oft aus. In Kapitel 3 zeigen wir, dass die chromatische Zahl von zufällig augmentierten Graphen χpertH,pfür jedes ε > 0nach oben durch χpertH,p≤(1 + ε)nlog(b) 2(log(n)−log(χ(H))) a.a.s. (3) beschränkt ist, wobei b= 1/(1 −p),solange p∈(0,1) konstant und χ(H)∈o (n) ist. Wir zeigen außerdem, dass Ungleichung 3 auch gilt, wenn p=p(n) = n−θfür ein θ∈(0,1/3) und χ(H)≤n1−3θgilt. Da dieser Beweis nicht konstruktiv ist, geben wir ein schwächeres konstruktives Resultat an. In Kapitel 4 zeigen wir, dass die obere Schranke für χpertH,paus Kapitel 3 auch für die listenchromatische Zahl von zufällig augmentierten Graphen gilt. So gilt für alle ε > 0 χlpertH,p≤(1 + ε)nlog(b) 2(log(n)−log(χ(H))) a.a.s. (4) wobei b= 1/(1 −p),solange p∈(0,1) konstant und χ(H)≤n−θfür ein θ∈(0,1) ist. In Kapitel 5 beweisen wir, dass Maker für jedes k≥2das biased Maker-Breaker k-Hamiltonkreisspiel in höchstens kn + o (n)Zügen gewinnen kann. Wir verwenden dieses Resultat, um zu zeigen, dass Maker das k-Kantenzusammenhangspiel in höchstens k 2n+o (n)Zügen gewinnen kann und dass Maker das k-Faktorspiel in höchstens lk 2mn+ o (n)Zügen gewinnen kann. In dem Fall des k-Kantenzusammenhangspiels stellt dies bis auf den o (n)Term die optimale obere Schranke dar. Die Schranke im k-Faktorspiel ist für gerade kscharf, während für ungerade kunter Umständen eine untere Schranke von k 2nmöglich wäre. In jedem dieser Spiele wurde die obere Schranke um einen Faktor größer als 8 gesenkt. Wir beweisen diese Resultate, indem wir eine expanderähnliche Struktur auf θn √log(n)Knoten und verschiedenfarbige Pfade, die die Grundlage der Hamiltonkreise bilden, konstruieren. Dieser Ansatz verallgemeinert ein Resultat von Brüstle et al., das besagt, dass Maker das Hamiltonkreisspiel in höchstens n+ o (n)Zügen gewinnen kann. 6
Chapter 1 Introduction 1.1 On the model of Randomly Augmented Graphs The most famous random graph model is the Gn,p model. Let p:N→(0,1) and let n∈N.We say that G= (V, E)is a Gn,p-graph (G∼ Gn,p) if |V|=nand each potential edge e∈V 2is chosen independently with probability p(n).In this thesis we will concentrate on two main cases. 1. pis constant or 2. pis some monotonously decreasing function, often in the shape p(n) = n−γ for some γ > 0. We further assume that V= [n].The Gn,p model was first introduced by Gilbert [Gil59] in 1959 and is highly related to the Gn,M random graph model introduced by Erdős and Rényi [ER59] where a random subset of size M≤nis chosen. Both of these models have been studied extensively. For a deeper analysis of the Gn,p model we refer the reader to the books of Bollobás [Bol85] and Frieze and Karoński [FK16]. In Chapter 3 and Chapter 4 of this thesis we study a generalization of the Gn,p random graph model. Consider a deterministic graph H= ([n], EH)and p:N→ (0,1) an arbitrary function. We define the randomly augmented graph pertH,p := H∪Gn,p as the union of the so-called host-graph Hand a random Gn,p-graph. Note that if His the empty graph, this model yields the random graph Gn,p. In their foundational paper [BFM03] Bohman et al. introduced a hybrid graph model, where the host-graph has at least linear (in n) minimum degree and the random graph is a Gn,M graph. In the current literature both of the random graph models described above have been studied as augmenting graphs. However, since in the existing literature the term perturbed graph is already heavily connected to the restriction on the minimum degree, see for example [CHMP20], [BMPP20] or [BPSS23], and the host graphs we are interested in are graphs Hwith bounded chromatic number χ(H),we decided to use the term augmented graph in this thesis. 7
1.2. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS 1.2 On the Chromatic Number of Random Graphs For a graph G= (V, E)the chromatic number χ(G)of Gis the minimum number of colors needed to color the vertices of Gsuch that no two adjacent vertices are of the same color. Since the number of colors in this chapter is not bounded by a constant number we will not use real colors {red, blue, . . .}but use the first few natural numbers as colors. This is standard procedure [Bol98]. That is, for a k∈N the function φ:V→[k]is called a k(vertex) coloring of G. φ is called a proper k-coloring of Gif {v, w} ∈ E=⇒φ(v)=φ(w). χ(G) := min {k:∃(φ:V→[k]) : {v, w} ∈ E=⇒φ(v)=φ(w)}. Note that often times a proper vertex k-coloring φ:V→[k]will be referred to as just a coloring of G, if the usage is clear from the context. Let φ:V→[k]be a proper coloring of Gthen, for each j∈[k]φ−1(j)is called the j-color class of G with respect to φ. Note that by definition each color class is an independent set in G. The chromatic number of the Gn,p model has been of interest for a long time. It was first studied by Erdős in [ER59] and its asymptotic behavior was first described by Bollobás [Bol88] who showed that for each ε > 0χ(Gn,p)≤(1 + ε)nlog(b) 2 log(n),if pis constant, or p=p(n)≥n−θ,for some θ∈(0,1/3) and b= 1/(1 −p). In this thesis we give a generalization for the result of Bollobás by showing that for each ε > 0 χpertH,p≤(1 + ε)nlog(b) 2 (log(n)−log(χ(H))) as long as pis constant. If p=p(n) = n−θ,for some θ∈(0,1/3),we can show the same upper bound as long as χ(H)≤n1−3θ.It is easy to see that this indeed is a generalization of the famous Bollobás result by plugging in the empty graph which has chromatic number 1. We achieve this result by considering an optimal coloring of Hand dividing its color classes into large color classes which have at least slightly below average size and small color classes which are even smaller. Building upon this we calculate the expected value of the chromatic numbers of the graphs induced by these color classes and finally apply McDiarmid’s bounded differences inequality [McD89]. We also show that for certain host graphs, for example the complete χ(H)-partite graph, this upper bound is tight. Furthermore, since the approach described above is non-constructive, we study an algorithm that colors the randomly augmented graph pertH,p by coloring the (purely random) graphs induced by the color classes of an optimal coloring of H. This yields the same upper bound as our non-constructive approach, but fails for host graphs of chromatic number at least n/ log(n)1/2. 8
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS ≤exp −cn2p7 log(n)8!. We consider the following implication of Theorem 2.5. Corollary 2.6 Let p∈(0,1) be constant. For any ε > 0and sufficiently large n=n(ε)∈Nwe have E(χ(Gn,p)) ≤(1 + ε)nlog(b) 2 log(n). Proof of Corollary 2.6. Let ε > 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 + ε 2nlog(b) 2 log(np)+nexp −cn2p7 log(n)8! (By Theorem 2.5 with ε′=ε/2) ≤1 + ε 2nlog(b) 2 log(np)+ε·nlog(b) 2·2 log(n)(2.4) = (1 + ε)nlog(b) 2 log(n). The inequality in (2.4) holds, since p(n)> n−1 7and thus nexp −cn2p7 log(n)8!≤nexp −cn log(n)8!≤ε·nlog(b) 2·2 log(n) As seen in the proof of Theorem 2.5, if pis constant, in the final step of Algorithm 2.1.1 it is possible to color the remaining vertices with a new color for each such vertex. This strategy is not successful in calculating a tight bound in case of p=p(n)∼n−θ. Here the number of remaining vertices is too large to be handled in such a way. To be able to analyze colorings of Gn,p for p=p(n)∼n−θwhere θ∈0,1 3we need a coloring algorithm for the small color classes. As Bollobás in [Bol88] we use the well-known greedy color algorithm. 15
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS Algorithm 2.1.2: Greedy Color Input: A random graph Gn,p Output: A coloring of the vertices of Gn,p 1while There is a set of uncolored vertices do 2Choose a maximally independent set Iof uncolored vertices; 3Color Iwith a new color; 4end We also give the following minor improvement of the result for the greedy color algorithm. Theorem 2.7 Let n−τ≤p≤n−θfor some arbitrary, but fixed τ, θ ∈0,1 3. Further let χg(Gn,p)be the number of colors used by Greedy Color. Then P χg(Gn,p)≥(1 + ε)nlog(b) log(np)!≤exp −(1 + o(1))n3. Proof of Theorem 2.7. We will follow the pattern of the proof in [FK16, Theorem 7.9] given for constant pwith slight modifications. Suppose that in some iteration of Algorithm 2.1.2 there are at least n0=np (logb(n))2vertices uncolored. Let Ube the set of uncolored vertices. Let κ=4 θand k1= logb(np)−κlogb(logb(n)). With the trivial estimate k1≤logb(np)≤logb(np)we get 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 that κis constant and thus (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 with 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 let Ube a set of cardinality n0, then P(∃S:|S| ≤ k1, S is a maximally independent set in U) ≤X S⊆U;|S|≤k1 P(Sis a maximally independent set in U) 16
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS = k1 X t=1 X S⊆U;|S|=t P(Sis a maximally independent set in U) = k1 X t=1 X S⊆U;|S|=t P(Sis an independent set in U) ·P(for each u∈(U\S)there exists s∈S:{u, s} ∈ E(Gn0,p)) = k1 X t=1 X S⊆U;|S|=t P(Sis an independent set in U) ·Y u∈U\S P(there exists s∈S:{u, s} ∈ E(Gn0,p)) = k1 X t=1 X S⊆U;|S|=t P(Sis an independent set in U) ·Y u∈U\S (1 −P(for all s∈S:{u, s}/∈E(Gn0,p))) = k1 X t=1 X S⊆U;|S|=t P(Sis an independent set in U) ·Y u∈U\S1−(1 −p)t = k1 X t=1 X S⊆U;|S|=t (1 −p)(t 2)1−(1 −p)tn0−t (since |U\S|=n0−t) = k1 X t=1 n t!(1 −p)(t 2)1−(1 −p)tn0−t ≤ k1 X t=1 ne t(1 −p)t−1 2t exp −(n0−t)(1 −p)t(since 1−x≤e−xfor all x) = k1 X t=1 (1 −p)(t 2) tt | {z } ≤1 ntexp (t) exp t(1 −p)texp −n0(1 −p)t ≤ k1 X t=1 ntexp t+t(1 −p)texp −n0(1 −p)t = k1 X t=1 nexp(1 + (1 −p)t)texp(−n0(1 −p |{z} =b−1 )t) ≤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 above) ≤exp −(1 ±o(1)) log(n)κ−2p−(κ−2)(with 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 the probability that in every set of at least n0vertices every maximally independent set is of size at least k1is at least 1−exp (−cn3).So in each step before the number of uncolored vertices drops below n0, at least k1vertices are colored. Therefore, the probability that more than (1 +ε)n logb(n)≥n k1+n0colors are used is at most exp (−(1 + o(1))n3). We now consider colorings of Gn,p using an asymptotically optimal amount of colors for the case p(n)≤n−θ. The following algorithm can be used to obtain a coloring which is an 1+εapproximation of an optimal coloring with a slightly better probability bound for p(n)∼n−θas in [Bol88]. This will be used later. Furthermore we use the following algorithm of Bollobás [Bol88]. Algorithm 2.1.3: Input: A random graph Gn,p Output: A coloring of the vertices of Gn,p 1while At least n log(np)vertices remain uncolored and if there is an uncolored independent set Iof size 2 logb(np)−4 logb(logb(np)) do 2Color Iwith a new color; 3end 4color the remaining graph using Algorithm 2.1.2; Lemma 2.8 Let n−τ≤p≤n−θfor some arbitrary, but fixed τ, θ ∈0,1 3. Then the probability that there exists a vertex set V1⊆Vof size ν(n) = n log(np)such that V1does not contain an independent set of size k0(ν)∼2 logb(np)∼2 logb(np)− 18
2.1. ON THE CHROMATIC NUMBER OF RANDOM GRAPHS 4 logb(log(np)) is bounded from above by P(∃S⊆[n] : |S|=ν∧α(Gn,p[S]) < k0(ν)) ≤exp − c2n2p3 log(n)6!!. Proof. Let ν=n log(np).We have 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 Theorem 2.3 for some constant 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 the last inequality holds for a constant c2>0and sufficiently large n, because log(np)≤log(nn−θ)≤(1 −θ) log(n). We also give the following minor improvement of a result of Bollobás using Algorithm 2.1.3 and Lemma 2.8. Theorem 2.9 Let θ∈0,1 3,δ > 0and n−1 3+δ≤p(n)≤n−θ. For sufficiently large n∈Nthere is a constant c > 0such that P χ(Gn,p)≥(1 + ε)np 2 log(np)!≤exp − cn2p3 log(n)6!!. Furthermore the probability that Algorithm 2.1.3 fails to construct a coloring with at most (1 + ε)np 2 log(np)colors is at most exp −cn2p3 log(n)6. Proof of Theorem 2.9. By Lemma 2.8 the probability that Algorithm 2.1.3 fails to find an independent set of size k1:= 2 logb(np)−logb(logb(np)) as long as at least ν=n log(n)vertices remain is at most exp −c2n2p3 log(n)6.Hence the number of colors used in the while-loop of Algorithm 2.1.3 is at most n k1≤(1+ ε 2)nlog(b) log(np). Furthermore, since the remaining νvertices induce a Gν,p, the probability that Algorithm 2.1.2 uses more than (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 } <1for sufficiently large n ≤ε 2 nlog(b) log(np) colors to color the remaining νvertices can be estimated by Theorem 2.7 to be at most exp −(1 + o(1))ν3= exp −(1 + o(1))n3 log(np)3!≤exp − (1 + o(1))n3 log(n)3!!.(a.4) Thus the probability that Algorithm 2.1.3 uses more than (1 + ε)nlog(b) 2 log(np)colors is at most P Algorithm 2.1.3 uses more than(1 + ε)nlog(b) 2 log(np)colors! ≤P(The while-loop of Algorithm 2.1.3 colors less than νvertices) +P Algorithm 2.1.2 uses more than ε 2 nlog(b) log(np)colors! ≤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!!, for some constant c3>0.The last inequality holds due to the fact that exp −(1+o(1))n3 log(n)3∈oexp −c2n2p3 log(n)6. Now we are able to give an upper bound for the expected value of χ(Gn,p). Corollary 2.10 Let θ∈0,1 3,δ > 0and n−1 3+δ≤p(n)≤n−θ. Let ε > 0. For sufficiently large n∈Nwe have E(χ(Gn,p)) ≤(1 + ε)np 2 log(np). Proof. Let ε > 0and k= (1 + ε 2)np 2 log(np). Let further nbe sufficiently large. 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 Theorem 2.9 with ε′:= ε/2) = (1 + ε)np 2 log(np). For the last inequality we use nexp − cn2p3 log(n)5!!≤np 2 log(np). This holds for sufficiently large n, because lim n→∞nexp − cn2p3 log(n)5!!= 0 and lim n→∞ np 2 log(np)=∞. In addition to these results that establish bounds on probabilities, we require the following basic result for the chromatic number of the union of any two graphs to analyze the chromatic number of pertH,p graphs. Lemma 2.11 (Divide and Color) Let G:= (V, EG)and H:= (V, EH)be graphs. Further let C ⊆ P(V)be a partition of Vsuch that every S∈ C is an independent set in G. Then χ(G∪H)≤X S∈C χ(H[S]) . If Gis a complete k-partite graph and Cis a k-partition of the vertices of Gas above, then χ(G∪H) = X S∈C χ(H[S]) . The proof is kind of folklore. For readers’ convenience we state it here briefly. Proof. For each S∈ C color the graph with χ(H[S]) colors that are not yet used. This is a proper coloring of G∪Hsince no edges in Gexist between vertices of the same color, as Cis a set of independent sets. Furthermore, by construction there are no edges in Hbetween vertices of the same color, since no color is used for vertices contained in different members of C. This proves the inequality. Let Gbe a complete k-partite graph and Cis a k-partition of the vertices of Vas above, the coloring is even optimal, since the H[S]are already optimally colored and for each pair of members of C, every edge between them already exists. Thus, every other proper coloring of the graph uses at least as many colors as the coloring constructed here. 21
2.2. ON THE CHOICE NUMBER OF RANDOM GRAPHS Furthermore, we require the following variation of the union bound which is a basic result of stochastic. Lemma 2.12 Let (Ω,Σ,P)be a probability space and k∈N.For each i∈[k]let Xi be a random variable and Aiin R.Then P k X i=1 Xi≤ k X i=1 Ai!≤ k X i=1 P(Xi≤Ai). Proof. Let ˜ Ω := nω∈Ω : Pk i=1 Xi(ω)>Pk i=1 Aioand for each i∈[k]let Ωi:= {ω∈Ω : Xi(ω)> Ai}.If for some ω∈Ωthere is Xi(ω)> Aifor all i∈[k],then 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 the Choice Number of Random Graphs The proof that the following result holds was first published by Alon [Alo93], who attributes it to private communication from Kahn. Lemma 2.13 (Kahn, Alon) Let G= (V, E)be a graph and b > 1be a constant, such that every set of at least n log(n)2vertices contains an independent set of size at least (1 −ε)2 logbn. Then χl(G)≤(1 + ε)n 2 logb(n). They then combined this result with the probability result of Bollobás. We will give the sightly stronger result relying on Lemma 2.4. This implies Theorem 2.14 (Variation of Kahn and Alon) Let 0<p<1be constant and ε > 0, then there exists n(ε)∈Nsuch that for all n≥n(ε) P χl(Gn,p)>(1 + ε)n 2 logb(n)!≤exp cn2 log(n)8!. Proof. By Lemma 2.4 every set of at least n/ log(n)2vertices contains an independent set of size at least (1−ε)2 logb(n).With probability at least 1−exp (cn2/log(n)8). Thus by Lemma 2.13 the probability that the choice number of GH,p exceeds (1 + ε)n 2 logb(n)is at most 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 the k-edge-Connectivity Game using Krivelevich’s techniques In this section we will prove the following result that is mentioned but not proven by Krivelevich [Kri10]. It is left as an exercise in [HKSS14, Excercise 6.7.2]. It is the currently best-known estimate for the number of rounds Maker needs to win the (1 : b)Maker-Breaker game for kedge-disjoint Hamilton cycles if b≤(1 −ε)n. Since I could not locate a proof, I will give one here. Theorem 2.15 (Remark of Krivelevich) Let ε > 0and k∈N.There exists n0∈N such that for every n∈N≥n0Maker has a strategy to construct kedge disjoint Hamilton cycles in the (1 : b)game played on the complete graph on nvertices in at most min(13n, (9k+ 3)n) + o (n)rounds for every b≤(1 −ε)n. In each step Maker will use the following algorithm to construct a graph of minimum degree min(8k+ 3,12) =: κin κn turns with positive probability. Note that the minimum can be avoided if k≥2which is the case we are most interested in. This algorithm is due to Gebauer and Szabo [GS09]. Algorithm 2.3.1: Algorithms for minimum degree game Input: A set B⊆Eclaimed by Breaker and a set M⊆Eclaimed by Maker Output: An edge e∈E\(B∪M) 1Choose a vertex v∈Vwith degM(v)< κ that maximizes dangv:= degB(v)−2bdegM(v); 2Choose a vertex w∈V\{v}such that {v, w}/∈(B∪M)is unclaimed uniformly at random. To prove Theorem 2.15 the following Lemma will be used. It is first stated by Krivelevich [Kri10] but was proved with techniques of Gebauer and Szabo [GS09]. It analyzes Algorithm 2.3.1. Lemma 2.16 (Krivelevich) For every ε > 0there exists a fixed δε>0such that by playing according to Algorithm 2.3.1, for all v∈VMaker chooses the κ-th edge incident in vat a time when dB(v)≤(1 −δε)nin the 1 : (1 −ε)n log(n)game. Further it can be shown that Maker constructed a (δεn, 2k)-expander with positive probability after κrounds by following Algorithm 2.3.1, where δε∈(0,1) is the same as in Lemma 2.16. Theorem 2.17 For every ε > 0Maker constructs a (δεn, 2k)-expander in at most κn rounds by following Algorithm 2.3.1 in each step in the (1 : (1 −ε)n log(n))game with positive probability. Proof. Suppose that Makers graph is not a (δεn, 2k)expander after Maker played each round by Algorithm 2.3.1 until each vertex had Maker degree κ. Then there exists a subset K⊆V S of size |A|=i≤δεnsuch that NM(K)⊆Lfor some L⊆V\Kwith |L|= 2si −1.Since the minimum degree in is Maker‘s graph is κ, we can assume that i≥5. 23
2.3. WINNING THE k-EDGE-CONNECTIVITY GAME USING KRIVELEVICH’S TECHNIQUES Excursion on i≥5: Assume that |K| ≤ 4.Since every vertex in Khas a minimum degree of κand at most 3of its neighbours are in K, we can assume that each element of Khas at least κ−3neighbours in V\K. In the worst case all vertices in Khave all neighbours outside of Ain common. We see that |NM(K)| ≥ κ−3.Since Mis supposed to be a(δεn, 2k)-expander, we need to ensure that |NM(K)| ≥ 2k|K|.This holds because |NM(K)| ≥ κ−3 = (8k+ 3) −3≥8k= 2k|K|. Furthermore there are at least κi 2edges of Maker incident in K. Now one of two cases holds. Case 1: At least κi 4edges were chosen from Kand went into K∪L. Case 2: At least κi 4edges were chosen from Land went into K. If at some point during the game a choice is made from a vertex v∈K, the Breaker degree in vis at most (1 −δε)nand the Maker degree is at most κ−1. Therefore there were at least δεn−κ+ 1 unclaimed edges incident to v. Thus the probability that Maker chose an edge such that the second endpoint belongs to K∪L is at most |K∪L|−1 δεn−κ+ 1 =2ki −1 + i−1 δεn−κ+ 1 =(2k+ 1)i−2 δεn−κ+ 1 regardless of the history of the game. Thus the probability that Case 1 holds, which is the case if such a choice has been made at least κi 4times. This is at most (2k+ 1)i−2 δεn−κ+ 1 !κi 4 . For a single choice made from v∈Lthe probability that the other endpoint is in Ais at most |K| δεn−κ+1 since as shown above at least δεn−κ+ 1 unclaimed edges were incident in vwhen the edge was chosen. Since at most κ|L|choices are made from L, the probability that at least κi 4of them end up in Kand thus Case 2 holds is at most κ|L| κi 4!i δεn−κ+ 1κi 4. Thus the probability that at least one of the Cases holds for a specific K⊆V with |K|=iis at most (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 42i δεnκi 4 24
3.2. BOUNDING THE CHROMATIC NUMBER OF pertH,p ≤ε 2·log(b)n 2 log(β(n)). The last inequality can be proved as follows. Let x:= β(n),c:= εlog(b) 4and a:= 1 + ε 2−1 2−1. Then for sufficiently large x, we have xa≤c log(x). Now we are ready to give an upper bound for the expected value of the chromatic number of an augmented graph. Theorem 3.3 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β:N→Nsuch that β(n)→ ∞ for n→ ∞. Let further p∈(0,1) be constant and b:= 1 1−p. Then for each ε > 0there is n(ε)∈Nsuch that for all n≥n(ε) EχpertH,p≤(1 + ε)·nlog(b) 2(log(n)−log(χ(H))). Proof. Let Cdenote the set of all color classes of an optimal coloring of Hand let ε > 0. Additionally, we define for g(n) = β(n)(1+ ε 2)−1 2the set of large color classes Lg={S∈ C||S| ≥ g(n)}and the set of small color classes Sg=C \ Lgas in Lemma 3.2. Note that a set S∈ Sg∪Lgis an independent set in H, because Sis a color class of an optimal (proper) coloring of H. So, the only edges in pertH,p[S]are the edges of Gn,p. We can thus identify pertH,p[S]with G|S|,p according to Remark 3.1. Furthermore, since pis constant the assumptions of Corollary 2.6 are fulfilled for sufficiently large n. Now EχpertH,p≤X S∈C EχpertH,p[S] =X S∈Lg EχpertH,p[S]+X S∈Sg EχpertH,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∈Lg1 + ε 21 2·log(b)|S| 2 log(|S|)+X S∈Sg|S| (for sufficiently large nby Corollary 2.6) ≤X S∈Lg1 + ε 21 2·log(b)|S| 2 log(|S|)+ε 2·nlog(b) 2 log(β(n)) (Lemma 3.2) ≤1 + ε 21 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 pertH,p ≤(1 + ε)·nlog(b) 2 log(β(n)) =(1 + ε)·nlog(b) 2(log(n)−log(χ(H))). We invoke the bounded differences inequality of C. McDiarmid [McD89]: Theorem 3.4 (McDiarmid’s inequality) Let X1, . . . , Xnbe independent random variables with Xjtaking values in some set Aj. Suppose that some measurable function f:Qn j=1 Aj→Rsatisfies |f(x)−f(x′)| ≤ cj whenever the vectors x, x′∈Qn j=1 Ajdiffer only in the j-th component. Let Ybe the (real valued) random variable Y:= f(X1, . . . , Xn). Then for any t > 0 P(|Y−E(Y)| ≥ t)≤2 exp −2t2 Pn j=1 c2 j!. Remark 3.5 In order to apply McDiarmid’s inequality to the chromatic number of pertH,p, we first set Xj:= {{i, j} ∈ E(pertH,p)|i<j}. Since the Xjform a partition of the edges of pertH,p, the random variable χpertH,pdepends solely on the values of the Xj. We set Y=f(X1, . . . , Xn) = χpertH,p the Xjbeing mutually independent random variables. Furthermore, for each j, if Xand ˆ Xonly differ in the j-th component, we have f(X)−f(ˆ X)≤1, since one additional color will always be enough to color the vertex j, if necessary. Thus, McDiarmid’s inequality is applicable with Pn j=1 c2 j=nand we the following upper bound for the chromatic number of pertH,p . Theorem 3.6 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β:N→Nsuch that β(n)→ ∞ for n→ ∞. Let further be p∈(0,1) and b=1 1−p. Then we have for each ε > 0and sufficiently large n χpertH,p≤(1 + ε)·nlog(b) 2(log(n)−log(χ(H))) a.a.s. Proof. Let ε > 0and λ=nlog(b) 2(log(n)−log(χ(H))). Now by Theorem 3.3 and McDiarmid’s inequality we get PχpertH,p≥(1 + ε)·λ =PχpertH,p−1 + ε 2·λ≥ε 2·λ 32
3.2. BOUNDING THE CHROMATIC NUMBER OF pertH,p ≤PχpertH,p−EχpertH,p≥ε 2·λ(Theorem 3.3) ≤2 exp −2 n· ελ 2!2 (McDiarmid’s inequality) ≤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−θfor some θ∈0,1 3 We consider now graphs from pertH,p with non-constant and small p. When trying to apply the same strategy as for constant p, it turns out that for small color classes it is not enough to merely count the number of vertices as in Lemma 3.2. The reason is that the number of vertices in small components can be of a higher order than the desired bound for the chromatic number of pertH,p. Instead we will use another implication of a result of Bollobás [Bol88]. This implies the following result which bounds the number of colors needed to color the small color classes of H. Lemma 3.7 Let ε > 0and H= ([n], E)be a deterministic graph with χ(H) = n β(n) for some function β:N→Q. Let further g(n) = β(n) log(n)and let Cthe set of all color classes of an optimal coloring of H. Define Lg={S∈ C||S| ≥ g(n)}and Sg=C\Lg. Let further n=n(ε)sufficiently large and p(n) = n−θ, where θ∈0,1 3 and b=1 1−p. If β(n)≥n3θ, then we have for n≥n(ε)for some n(ε)∈N, E χ pertH,p "[ C∈Sg C#!!≤εnp 2(log(np)−log(χ(H))). Proof. According to Remark 3.1, for each C∈ Sgwe can identify pertH,p(n)[C]with G|C|,p(n). So by invoking Corollary 2.10 with ε=1 3we get EχpertH,p(n)[C]=EχG|C|,p(n) ≤EχG|g(n)|,p(n) (since |C| ≤ g(n)) ≤1 + 1 3g(n)p(n) 2 log(g(n)p(n)) (Corollary 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 pertH,p ≤β(n)p(n) log(n) log(β(n)p(n)). Thus, since |Sg| ≤ χ(H)≤n β(n)we have EχpertH,p [∪C∈SgC]≤X C∈Sg EχpertH,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)(for nlarge enough) =εnp 2(log(np)−log(χ(H))). Next, we bound the expectation of χpertH,pfrom above using Lemma 3.7. Theorem 3.8 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β:N→Q. Let further ε > 0and p(n) = n−θ, where θ∈0,1 3and b=1 1−p. If β(n)≥n3(θ+δ)for some constant δ > 0, then there exists n(ε)∈Nso that for all n≥n(ε)we have EχpertH,p≤(1 + ε)·np 2(log(np)−log(χ(H))). Proof. Let Cdenote the set of all color classes of an optimal coloring of Hand let ε > 0. Additionally we define for g(n) = β(n) log(n)the set of large color classes Lg={S∈ C||S| ≥ g(n)}and the set of small color classes Sg=C \Lg. For a large color class S∈ Lgof an optimal coloring of Hthere are no edges of Hwithin S. So we can identify pertH,p(n)[S]with G|S|,p(n),by Remark 3.1. Since |S| ≥ g(n) = β(n) log(n)≥n3(θ+δ 2)for sufficiently large n, we have p(n) = n−θ≥ |S|−θ 3(θ+δ/2) =|S|−1 3+δ 6(θ+δ/2) , and we may invoke Corollary 2.10 with ε′=1 + ε 21 2−1>0and get EχpertH,p[S]=EχG|S|,p(n)≤1 + ε 21 2p|S| 2 log(|S|p).(3.1) For sufficiently large n, log(log(n)) ∈o ((log(β(n)))) .Thus 1 + ε 21 2log(g(n)) = 1 + ε 21 2(log(β(n)) −log(log(n)) | {z } =o(log(β(n))) )≥log(β(n)).(3.2) 34
3.2. BOUNDING THE CHROMATIC NUMBER OF pertH,p Now EχpertH,p≤X S∈C EχpertH,p[S](Lemma 2.11) =X S∈Lg EχpertH,p[S]+X C∈Sg EχpertH,p[S] =X S∈Lg EχG|S|,p+X C∈Sg EχG|S|,p (Remark 3.1) ≤X S∈Lg1 + ε 21 2p|S| 2 log(|S|p)+X C∈Sg EχG|S|,p (with (3.1)) ≤X S∈Lg1 + ε 21 2p|S| 2 log(|S|p)+ε 2·np 2 log(β(n)p) (Lemma 3.7 for n≥n(ε)for some n(ε)∈N) ≤X S∈Lg1 + ε 21 2p|S| 2 log(g(n)p)+ε 2·np 2 log(β(n)p)(|S| ≥ g(n)) =1 + ε 21 2pPS∈Lg|S| 2 log(g(n)p)+ε 2·np 2 log(β(n)p) ≤1 + ε 21 2pn 2 log(g(n)p)+ε 2·np 2 log(β(n)p) ≤1 + ε 2pn 2 log(β(n)p)+ε 2·np 2 log(β(n)p)(with (3.2)) = (1 + ε)pn 2(log(np)−log(χ(H))) The main result of this section is the following theorem, where we use McDiarmid’s bounded differences inequality (Theorem 3.4) to bound the probability that χpertH,pdiffers from its expectation by a large amount. Theorem 3.9 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β:N→Q.Let further p(n)≥n−θ, where θ∈0,1 3and b=1 1−p. If β(n)≥n3θ, then χpertH,p≤(1 + ε)·np 2(log(np)−log(χ(H))) a.a.s. Proof. Let ε > 0and λ=εn log(b) 4(log(np)−log(χ(H))) .We have P χpertH,p≥(1 + ε)nlog(b) 2(log(np)−log(χ(H)))! =P χpertH,p≥1 + ε 2nlog(b) 2(log(np)−log(χ(H))) +λ! ≤PχpertH,p≥EχpertH,p+λ(Theorem 3.8) 35
3.3. TIGHTNESS OF UPPER BOUNDS FOR CERTAIN GRAPHS ≤2 exp −λ2 2n!(McDiarmid’s inequality, Theorem 3.4) ≤2 exp − ε2np2 32(log(n)−log(χ(H)))2!! (by Remark 2.1 and log(np)≤log(n)) ≤exp −n1 4, and the last inequality holds, because p≥n−θ,θ∈(0,1 3)implies np2≥n1/3. 3.3 Tightness of upper bounds for certain graphs We proved an upper bound for the chromatic number of an augmented graph, depending only on pand the chromatic number of the host graph. A natural question is, of course, whether our bounds are tight. Indeed, the next theorem shows that there exist host graphs for which the asymptotics for the chromatic number is equal to the asymptotics of the upper bound in Theorem 3.6. We will prove this by considering the independence number of a certain class of host graphs. These host graphs are characterized by a "low" number of "large" independent sets. As an example one can consider the complete χ(H)-partite graphs. Lemma 3.10 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β=β(n)with β(n)→ ∞ as n→ ∞. Further let k=l2(log(n)−log(χ(H))) log(b)m and nH,k the number of independent sets of size kin H. If nH,k ∈oχ(H) n−k+1, then α(pertH,p)≤2(log(n)−log(χ(H))) log(b)a.a.s. Proof. Let Xkbe the random variable that counts the number of independent sets of size kin pertH,p. Now Pα(pertH,p)≥k=P(Xk≥1) ≤E(Xk)(Markov’s inequality) =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), with our assumption on nH,k. Together with the well-known inequality χ(G)≥n α(G)Lemma 3.10 implies Theorem 3.11: 36
3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL CHROMATIC NUMBER Theorem 3.11 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β=β(n)with β(n)→ ∞as n→ ∞. Further let k=l2(log(n)−log(χ(H))) log(b)m and nH,k the number of independent ksets, in H. If nH,k ∈oχ(H) n−k+1, then for each ε > 0there is a n(ε)∈N, so that for all n≥n(ε)we have 1. α(pertH,p)≤2(log(n)−log(χ(H))) log(b)a.a.s. 2. χpertH,p≥(1 −ε)·nlog(b) 2(log(n)−log(χ(H))) a.a.s. 3.4 Coloring Augmented Graphs with Host Graphs of small Chromatic Number The proofs of Theorem 3.6 and Theorem 3.9 rely on McDiarmid’s bounded differences inequality and are not constructive. In this section we will give algorithms based on algorithms of Bollobás [Bol88] (in the following Algorithm 2.1.1 and Algorithm 2.1.3). They find a coloring of pertH,p with at most (1 + ε)·nlog(b) 2(log(n)−log(χ(H))) colors a.a.s. We restrict ourselves to host graphs Hwith χ(H)≤n log(n)γfor some constant γ≥1 2in the case that pis constant and host graphs with χ(H)≤n1−3θ−2δ 2 for some arbitrary small constant δ > 0if p(n) = n−θ. In preparation for the rest of the section we define the sets of large and small color classes analogously to section 3.2. The Algorithms 3.4.1, 3.4.2, 2.1.1 and 2.1.3 have exponential time complexity. Definition 3.12 Let H= ([n], E)be a deterministic graph. Let fbe a coloring of Hand Cthe set of all color classes with respect to f. Let further g:N→Rbe a function. We define Sg:= {S∈ C||S|< g(n)}and Lg:= {S∈ C||S| ≥ g(n)}. Sgis the set of small and Lgis the set of large color classes with respect to f. We will use Algorithm 2.1.1 to color the large color classes of Hwhile Theorem 2.5 allows us to bound the probability that this approach fails to yield a coloring with a small number of colors. We use the following algorithm to construct a proper coloring of pertH,p. Algorithm 3.4.1: Coloring pertH,p Input: A deterministic graph Hwith χ(H)≤n β(n)where β(n)≥log(n)γ for some constant γ > 1 2, an augmented graph G= pertH,p for some constant p∈(0,1) and ε > 0with ε < 2(2γ−1). Output: A proper coloring of Gusing less than (1 + ε)·nlog(b) 2(log(n)−log(χ(H))) colors. 1Construct an optimal coloring χ′of H; 2In each color class Sof χ′with |S| ≥ β(n)(1+ ε 2)−1 2=: g(n)construct a proper coloring using Algorithm 2.1.1; 3Color each vertex that is still uncolored with its own color; 37
3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL CHROMATIC NUMBER Theorem 3.13 Let H= ([n], E)be a deterministic graph with χ(H)≤n log(n)γfor some constant γ > 1 2and let β(n) = n χ(H). Let further p∈(0,1) be constant and b=1 1−p. Then Algorithm 3.4.1 a.a.s.constructs a proper coloring for pertH,p using at most (1 + ε)·nlog(b) 2(log(n)−log(χ(H))) colors. Proof. Since this algorithm constructs a proper coloring, the only thing left to prove is that it uses at most (1 + ε)·nlog(b) 2(log(n)−log(χ(H))) colors a.a.s.. We will show that for coloring the large color classes of Hat most (1 + ε 2)·nlog(b) 2(log(n)−log(χ(H))) colors are used a.a.s.. Since by Lemma 3.2 there are at most ε 2·log(b)n 2 log(n)vertices of pertH,p left uncolored, the total number of colors used is at most as stated in the theorem. For each S⊆[n], let ξ(pertH,p[S]) be the number of colors that were used by Algorithm 3.4.1 to color the vertices of S. First we recall some preliminary facts: each S∈ Lgis an independent set in Hthus pertH,p[S]can be identified with G|S|,p (see Remark 3.1). According to Theorem 2.5, Algorithm 2.1.1 uses more than 1 + ε 2log(b)n 2 log(n)colors to color Gn,p with probability at most exp −cn2 log(n)8for some constant c > 0. Note that the probability pis constant by the assumption of the theorem and thus the term cp7from Theorem 2.5 is constant here. Choose ε′>0 such that 1+ε′=1 + ε 21 2.Combining these facts we get for each color class S∈ Lg P ξpertH,p[S]≥1 + ε 21 2log(b)|S| 2 log(|S|)! =P ξG|S|,p≥1 + ε 21 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) for some constant c > 0. We will use χ(H) = n β(n)≤n log(n)1 2 and thus log(β(n)) ≥log log(n)1 2=1 2log(log(n)). (3.4) And continue P X S∈Lg ξpertH,p[S]≥1 + ε 2·log(b)n 2(log(n)−log(χ(H)))! =P X S∈Lg ξpertH,p[S]≥1 + ε 2·log(b)n 2 log(β(n))! ≤P X S∈Lg ξpertH,p[S]≥1 + ε 21 2·log(b)PS∈Lg|S| 2 log(g(n)) !(since X S∈Lg|S| ≤ n) =P X S∈Lg ξpertH,p[S]≥X S∈Lg1 + ε 21 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 ξpertH,p[S]≥X S∈Lg1 + ε 21 2·log(b)|S| 2 log(|S|)!(since g(n)≥ |S|) ≤X S∈Lg P ξpertH,p[S]≥1 + ε 21 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 increasing function) ≤χ(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 (for 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 (for some c′′ >0by 3.4) =o(1).(since γ≥1 2) We proceed to color an augmented graph, where p(n) = n−θfor some θ∈0,1 3. We need the greedy algorithm Algorithm 2.1.2 to color the small color classes. Based on these results we use the following algorithm. Algorithm 3.4.2: A coloring of pertH,p Input: A constant θ∈0,1 3, an edge probability pwith p=p(n) = n−θ, a deterministic graph Hwith χ(H)≤n β(n)where β(n)≥n3θ 2+δfor some δ > 0arbitrary, but fixed and a perturbed graph G= pertH,p. Further an ε > 0arbitrary small but fixed. Output: A proper coloring of Gusing less than (1 + ε)·nlog(b) 2(log(n)−log(χ(H))) colors. 1Construct an optimal coloring χ′of H; 2In each color class Sof χ′with |S| ≥ β(n) log(n)=: g(n)construct a proper coloring using Algorithm 2.1.3; 3Color each remaining color class of Hwith the greedy algorithm Algorithm 2.1.2; Theorem 3.14 Let H= ([n], E)be a deterministic graph with χ(H) = n β(n)for some function β:N→Qsuch that β(n)→ ∞ for n→ ∞. Let further be 39
3.4. COLORING AUGMENTED GRAPHS WITH HOST GRAPHS OF SMALL CHROMATIC NUMBER p=p(n) = n−θfor some constant θ∈(0,1 3), let b=1 1−pand ε > 0. If β(n)≥ n3θ+ε, Algorithm 3.4.2 a.a.s.constructs a proper coloring of pertH,p with at most (1 + ε)nlog(b) 2(log(n)−log(χ(H))) colors. Proof. Let ξ(pertH,p)be the number of colors used by Algorithm 3.4.2. Since this algorithm yields a proper coloring, it is left to prove that ξ(pertH,p)≤(1 + ε)nlog(b) 2(log(n)−log(χ(H))) a.a.s. With g=g(n) = β(n) log(n)we consider Sgas well as Lg. We split our proof into two parts. First we prove that all "small" color classes are colored using at most ε 2 nlog(b) 2(log(n)−log(χ(H))) colors. Next we will prove that all "large" color classes are colored with at most 1 + ε 2nlog(b) 2(log(n)−log(χ(H))) colors. Claim 1: ξ(pertH,p [SS∈SgS]) <ε 2 nlog(b) 2(log(n)−log(χ(H))) a.a.s. Proof of Claim 1: Let χg(Gn,p)be the number of colors that are used when coloring Gn,p with the greedy Algorithm 2.1.2. Since for each S∈ Sgthe graph pertH,p[S]has the same distribution as the random graph G|S|,p(n)by Remark 3.1. We may consider the random graph Gg(n),p(n)in which each set of |S|vertices induces aG|S|,p(n). Thus, the greedy algorithm uses at least as many colors to color Gg(n),p(n) as for pertH,p[S].Since Algorithm 3.4.2 uses the greedy Algorithm 2.1.2 to color S, we get ξ(pertH,p[S]) = χg(G|S|,p(n))where χg(G|S|,p(n))is the number of colors used by Algorithm 2.1.2 to color G|S|,p(n). Thus for all q∈Rwe have, Pξ(pertH,p(n)[S]) ≥q=Pχg(G|S|,p(n))≥q≤Pχg(Gg(n),p(n))≥q.(3.5) Now P ξ pertH,p "[ S∈Sg S#!≥ε 2·nlog(b) 2(log(n)−log(χ(H) | {z } =log(β(n)) )) ≤P X S∈Sg ξ(pertH,p[S]) ≥ε 2·nlog(b) 2 log(β(n))! ≤P X S∈Sg ξ(pertH,p[S]) ≥ε 2·PS∈Sgβ(n) log(b) 2 log(β(n)) !(n≥PS∈Sgβ(n)) ≤X S∈Sg P ξ(pertH,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 inequality 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 Theorem 2.7) 40
4.2. BOUNDING THE CHOICE NUMBER OF RANDOMLY AUGMENTED GRAPHS Thus, P Xv≤1 + ε 2·|Vi|log(b) 2·log(|Vi|)! =P Xv≤E(Xv)−ε 2·|Vi|log(b) 2·log(|Vi|)!(by equation 4.1) ≤P Xv−E(Xv)≤ −ε|Vi|log(b) 4·log(|Vi|)! ≤P Xv−E(Xv)≤ −εg(n) log(b) 4·log(g(n))! (since x/ log(x)is monotonously increasing) ≤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)!(for some constant c1>0) ≤exp(−c1nc2) for some constant c2>0,since γ < 1 2and ε < 2(1 −γ)−1. Thus P ∃Vi∈ Lg:∃v∈Vi∧Xv≤1 + ε 2|Vi|log(b) 2 log(|Vi|)! ≤X Vi∈LgX v∈Vi P Xv≤1 + ε 2|Vi|log(b) 2 log(|Vi|)!(Union Bound) ≤nexp (−c1nc2) =o(1). So, with positive probability, to every vertex that belongs to a large color class Vi∈ Lgof Hat least 1 + ε 2|Vi|log(b) 2 log(|Vi|)colors are assigned. Proof of Theorem 4.1. By Lemma 4.4, with positive probability to each vertex in a large color class Vi∈ Lgof Hat least 1 + ε 2·|Vi|log(b) (log(n)−log(χ(H))) colors are assigned. By the probabilistic method there exists a function ˆ f:U→ C such that for each Vi∈ Lgand each v∈Viwe have |ˆ f−1(Vi)∩Uv| ≥ 1 + ε 2·|Vi|log(b) (log(n)−log(χ(H))) and ˆ f−1(Vi)∩ˆ f−1(Vj) = ∅for 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),the probability that Vidoes not have a list coloring using only the colors assigned to it by ˆ fis at most exp −cg(n)2 log(g(n)8) by Theorem 2.14. This implies that the probability that there exists a Vi∈ Lgthat does not have a list coloring using only the colors randomly attributed to it by f, is at most P ∃Vi∈ Lg:χlpertH,p[Vi]≥1 + ε 2·|Vi|log(b) (log(n)−log(χ(H)))! (by the union bound) ≤X Vi∈Lg P χlpertH,p[Vi]≥1 + ε 2·|Vi|log(b) (log(n)−log(χ(H)))! =X Vi∈Lg P χlG|Vi|,p≥1 + ε 2·|Vi|log(b) (log(n)−log(χ(H)))! ≤X Vi∈Lg exp −cg(n)2 log(g(n)8)!(by Theorem 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 above, for each Vi∈ Lgthere exists a coloring φi:Vi→Uof pertH,p[Vi] using only colors assigned to Viby ˆ fa.a.s. We combine these colorings by setting φLg(v) = φVi(v)for each v∈Vi.Since ˆ fmaps each color to exactly one color class, no two neighbors can have the same colors with respect to φLg.This implies that φLgis a proper coloring of the large color classes which uses at most 1 + ε 2·nlog(b) (log(n)−log(χ(H))). After having colored the large color classes, for each v∈Vthere are at least ε 2·nlog(b) (log(n)−log(χ(H))) colors in Uvthat have not yet been used. We consider the bipartite graph Gb= (A˙ ∪B)with the vertices of pertH,p that are in small color classes of C on one side, i.e. A={v∈V:∃Vi∈ Sv∈Vi}and the colors that are not used by φLgon the other side, i.e. B={c∈U∧c /∈Im (φLg)}.For every vertex v∈A and color c∈Bwe add the edge {v, c}iff c∈Uv.As shown in Lemma 3.2 at most ε 2·nlog(b) (log(n)−log(χ(H))) vertices remain uncolored. This implies |A| ≤ ε 2·nlog(b) (log(n)−log(χ(H))) Furthermore, for each v∈Awe have |NGb(v)|≥|Uv|−|Im (Lg)| ≥ ε 2·nlog(b) (log(n)−log(χ(H))) because φLgused at most 1 + ε 2·nlog(b) (log(n)−log(χ(H))) colors. So, for every ∅ =A′⊆A and v∈A′we have |NGb(A′)| ≥ |NGb(v)| ≥ ε 2·nlog(b) (log(n)−log(χ(H))) ≥ |A|≥|A′| 48
4.3. REMARKS ON TIGHTNESS Thus by the use of Hall’s Marriage Theorem there exists a Matching Mthat covers A. The matching Minduces a list coloring φSgwith respect to Ufor the vertices in small color classes using only the remaining colors in the following sense φSg(v) = c iff {v, c} ∈ M. Since φSgand φLguse disjunct sets of colors, we define the following proper list coloring of pertH,p with respect to U. φ:V→U, v 7→ φLg(v),∃Vi∈ Lg:v∈Vi φSg(v),∃Vi∈ Sg:v∈Vi 4.3 Remarks on tightness After proving an upper bound for χlpertH,pfor the cases in which p∈(0,1) is constant and χ(H)< nγfor some γ < 1/2,we will investigate whether for some combinations of Hand pthe bound in Theorem 4.1 is tight. Our first remark considers host graphs of small chromatic number. Lemma 4.5 Let Hbe a deterministic graph such that χ(H)is bounded by a constant. Then for all constant p∈(0,1) and ε > 0we have χlpertH,p≥nlog(b) 2 (log(n)−log(χ(H))) a.a.s. Proof. Finding a proper k-coloring of a graph Gis equivalent to finding a proper list-coloring of Gwith respect to the family U={[k]}v∈V,so χ(G)≤χl(G).The well-known result χ(G)≤n/α(G)combined with a result of Bollobás and Erdős [BE76] that says α(Gn,p)≤2 log(b)−1(1 −ε)−1/2log(n)a.a.s., we get q(1 −ε)nlog(b) 2 log(n)≤n α(Gn,p)≤χ(Gn,p)≤χl(Gn,p)a.a.s. By assumption of the lemma χ(H)is bounded by a constant, so log(χ(H)) ∈ o (log(n)) and there exists nε∈Nsuch that for all n≥nε (1 −ε)−1/2(log(n)−log(χ(H))) ≥log(n). This implies for 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)≤χlpertH,p. 49
4.4. CONCLUSION The following result shows that the bound in Theorem 4.1 is indeed tight in the following sense: Theorem 4.6 Let H= ([n], E)be a deterministic graph with χ(H) = nγfor some γ < 1/2.Further let k=l2(log(n)−log(χ(H))) log(b)mand nH,k the number of independent k sets, in H. If nH,k ∈oχ(H) n−k+1, then for each ε > 0there is a nε∈N, so that for all n≥nεwe have χlpertH,p≥(1 −ε)·nlog(b) 2(log(n)−log(χ(H))) a.a.s. Proof. Since χ(H) = nγthe prerequisites of Theorem 3.11 are satisfied. This implies χlpertH,p≥χpertH,p≥(1 −ε)·nlog(b) 2(log(n)−log(χ(H))) a.a.s. 4.4 Conclusion In this chapter we proved that for host graphs Hwith chromatic number χ(H)≤nγ, for some γ < 1/2and p∈(0,1) constant, the chromatic number of the randomly augmented graph pertH,p is a.a.s. bounded from above by χlpertH,p≤nlog(b) 2(log(n)−log(χ(H))).(4.3) This is the same upper bound that was proved for the chromatic number in Chapter 3. Furthermore, we proved that this bound is tight for certain host graphs that contain only few independent sets of a certain size. All of these results show that χlpertH,pin these cases behaves in the same way as χpertH,p. The following natural questions arise: Question 1 : Does the upper bound in 4.3 hold for all randomly augmented graphs pertH,p as long as p∈(0,1) is constant and Hsatisfies χ(H)∈o (n)? Question 2 : For which combinations of host graphs Hand probability functions p:N→(0,1) can a similar bound be shown? Question 3 : Can the technique used in this chapter be used to show similar bounds for related invariants? We suggest the game chromatic number and the quantum chromatic number as natural candidates. 50
Chapter 5 An Algorithm to win the biased k-Edge-Connectivity and k-Factor Games fast 5.1 Introduction 5.1.1 Previous work The biased Maker-Breaker-Connectivity game was first introduced by Chvátal and Erdős [CE78]. They proved the following upper bound for its critical bias. Theorem 5.1 (Chvátal and Erdős, [CE78]) Let ε > 0,then there exists n(ε)∈N, such that for each n≥n(ε)and b > (1+ε)n log(n),Breaker wins the (1−b)connectivity game. This is achieved by isolating a single vertex v∈V, i.e. assuring that at the end of the game its Maker degree is zero and its Breaker degree is n−1.Since Hamiltonicity implies connectivity, this also implies that Breaker wins the Hamiltonicity game, and most other games that require Maker to build a global structure, with the same parameters. Krivelevich [Kri10] proved the following theorem for the biased Hamiltonian cycle game determining the asymptotically exact critical bias for this game to be (1 + o(1)) n log(n). Theorem 5.2 (Krivelevich 2010, [Kri10]) There exists n0∈Nsuch that for every n∈N≥n0Maker has a strategy to win the (1 : b)Hamiltonian cycle game played on the complete graph on nvertices in at most 14nrounds for every b≤ 1−30 log1/4(n)n. This result is achieved in three steps. In the first step an expander graph is created by Maker. In the second step the connected components of the expander graph are connected by Maker and a connected expander is achieved. In the last step, the Hamiltonian cycle is completed by adding boosters to Maker‘s graph. Krivelevich also remarks that this strategy can be generalized. We remind the reader of Theorem 2.15. 51
5.1. INTRODUCTION Theorem 5.3 (Theorem 2.15) Let ε > 0and k∈N.There exists n0∈Nsuch that for every n∈N≥n0Maker has a strategy to construct kedge disjoint Hamiltonian cycles in the (1 : b)game played on the complete graph on nvertices in at most min(13n, (8k+ 1)n)rounds for every b≤(1 −ε)n. We now consider a graph G= (V, E)in which Eis the pairwise disjoint union of kHamiltonian cycles. Then each vertex v∈Vhas degree exactly 2k. Thus G is a 2k-factor. Furthermore, for two distinct vertices v, w ∈Vthere exist 2kedge disjoint paths connecting v, w. This is true because each Hamiltonian cycle induces two paths from vto w. The techniques of Krivelevich yield a lower bound for the critical bias in the (1 : b) 2k-edge-connectivity game and in the (1 : b) 2k-factor game and show that both games can be won in a linear number of rounds. Since the critical bias is known asymptotically, it is further of interest how many rounds Maker has to play to claim a winning graph. We note the following: Remark 5.4 (Lower Bound) A Hamiltonian graph has to contain a Hamiltonian cycle, which contains exactly nedges. Since Maker can only add one edge per round, Maker cannot win in fewer than nrounds. For k≥2,if Gis k-edge-connected, its minimum degree has to be at least k. Otherwise it would be possible to destroy its connectivity by removing every edge incident in a vertex vwith deg(v)< k. Since every edge connects exactly to vertices, the minimum number of edges needed is lk 2nm.Since Maker can add only one edge per round, Maker cannot win in fewer than lk 2nmrounds. For the case k= 1 Brüstle et al. [BCN+23] showed the following improvement of Krivelevich‘s result. Theorem 5.5 (Brüstle et al. 2023, [BCN+23]) There exists a constant C > 0and n0∈Nsuch that for any b < n log(n)−Cn log(n)3/2and n≥n0Maker wins the (1 : b) Hamilton cycle game on the complete graph on nvertices in at most n+Cn √log(n) rounds. 5.1.2 Our results Remark 5.6 Since an edge disjoint union of kHamiltonian cycles consists of kn edges, Maker needs at least kn rounds to win this (1 : b)game. Thus for the case k= 1,Theorem 5.5 states essentially the fastest possible round-complexity, up to the Cn √log(n)=o(n)term. Analogously, our main theorem gives the fastest roundcomplexity, up to an o(n)term in the k-edge-connectivity game and the 2k-factor game: Theorem 5.7 (Main Theorem) Let k∈Nbe arbitrary but fixed. There exists a constant Ck>0and n0∈Nsuch that for any b < n log(n)−Ckn log(n)3/2and n≥n0Maker has a strategy to construct kedge disjoint Hamiltonian cycles in the (1 : b)game on the complete graph on nvertices in at most kn +Ckn √log(n)rounds. The main theorem immediately implies a few additional results: 52
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES Theorem 5.8 Let k∈Nbe arbitrary but fixed. There exists a constant Ck>0and n0∈Nsuch that for any b < n log(n)−Ckn log(n)3/2and n≥n0Maker has a strategy to win (1 : b)k-factor-game on the complete graph on nvertices in at most lk 2mn+Ckn √log(n) rounds. Proof of Theorem 5.8. If kis even, Maker builds k 2Hamiltonian cycles with the algorithm used in the proof of the main theorem Theorem 5.7 and these cycles form a k-factor. If kis odd, Maker builds k+1 2=lk 2mHamiltonian cycles with the algorithm used in the proof of the main Theorem and then chooses one of the Hamiltonian cycles to remove every second vertex in it. By this deletion process, we have created a k-factor. Theorem 5.9 Let k∈N≥2be arbitrary but fixed. There exists a constant Ck>0 and n0∈Nsuch that for any b < n log(n)−Ckn log(n)3/2and n≥n0Maker has a strategy to win the (1 : b)k-edge-connectivity-game on the complete graph on nvertices in at most k 2+Ckn √log(n)rounds. 5.1.3 Methods and Innovations In this chapter we use techniques that are similar to those used in a paper of Brüstle et al. [BCN+23] that gives an algorithm to win the (1 : b)Hamiltonian cycle game in asymptotically optimal time. Since, in contrast to Brüstle et al., we are interested in building multiple edge-disjoint Hamiltonian cycles, we have to build the foundation for these cycles simultaneously. Where Brüstle et al. built a single set of paths that will be joined to form the single Hamiltonian cycle, we build kedge disjoint sets of paths of different colors simultaneously. As in [BCN+23] we use an expander-like subset of Vto facilitate rotations similar to those introduced by Pósa [Pó76]. However, since we want to construct k≥1edgedisjoint Hamilton cycles, we cannot use these edges in multiple Hailton cycles. Thus we increase the required minimum degree of these vertices to 34kwhere Brüstle et al. only required a minimum degree of 10. This increase in the minimum degree also ensures that the expander-like subset remains connected and keeps expander-like properties even if all kHamiltonian cycles were removed at the end of the game. In addition to these modifications we present an innovative strategy that ensures k-connectivity based on the structure that arises at the end of the algorithm Hamilton-Cycles. 5.2 Describing the Algorithm Hamilton-Cycles In the algorithm Hamilton-Cycles we encounter cases in which one vertex is determined first and Maker is supposed to add an edge to this vertex. Since some of our proofs rely on the fact that a certain amount of random edges were added to each vertex vof a certain subset of V, we want to "ignore" the edges which are incident in vbut were chosen from some w∈V\ {v}.To achieve this we consider some edges to be directed edges. Whenever we call for Maker to claim the directed edge 53
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES (v, w),Maker chooses the edge {v, w}and denotes that the directed edge (v, w)was supposed to be taken. However, this is only a bookkeeping measure. This approach leads to the following problem: Let v, w ∈V. What is Maker supposed to do if the algorithm Hamilton-Cycles calls for the addition of the directed edge (v, w),but {v, w}was already claimed as the directed edge (w, v)? This is easily remedied. Whenever this is the case Maker updates her bookkeeping by including the directed edge (w, v).Since Maker did not have to claim an edge (as {w, v}={v, w}had already been chosen), Maker takes another turn according to the algorithm Hamilton-Cycles immediately with an updated out-degree of v. We define the degree in Breakers graph of some v∈Vas dB(v).We call a vertex v∈Vtroublesome if dB(v)≥n √log(n).We further define the number of out-edges Maker added to vafter it became troublesome as d∗ M(v)and the number of out-edges Maker added to vbefore it became troublesome as d′ M(v).Further we define in each step for every v∈V, dang(v) := dB(v)−bd∗ M(v).These notations are consistent with [BCN+23]. In the first stage we create a set Siof size On √log(n)and a set Piof families of paths in V\Si.We also make sure that the paths are not too long i.e. each such path has a length of at most log(n).The relevance of bounding the length will become apparent in Stage 3, when we want to connect the vertices of the paths to ensure connectivity. For clarity we color all edges that are picked with a color between 0and k, where edges colored with a color i, 1≤i≤kwill be used to form the i-th Hamiltonian cycle, while the edges colored with 0are all-purpose edges not yet committed to one of the Hamiltonian cycles. We call v, w ∈V\Sij-neighbors, if they are joined by an edge of color j. For each round i, color j∈[k]and v∈V\Si,we define [v](j) ito be the path of color j that contains v. At the beginning we choose S0⊆Varbitrary with S0=1000(4k+3)2√k+2n √log(n),and for each j∈[k]we define P(j) 0to be the set of all singleton paths in V\S0,where a singleton path consists of one vertex only. 5.2.1 Stage 1: Creating a Graph consisting of an Expander and few paths If, after round iof Breaker a vertex v∈V\Sihas become troublesome, it is added to Si−1and for each j, we delete the path [v](j) i−1=P1◦v◦P1that contains v, from P(j) i.Furthermore, all Maker-edges incident in vare recolored with k+1.Thereafter the paths P1and P2are added to P(j) i. Two paths P, P′∈ Pj iof length less than log(n)are called (u, v)-available in Pj i if uis an endpoint of P, v is an endpoint of P′,{u, v}is still unclaimed and no edges of color k+ 1 are incident in uor v. This implies that until this point there was at most one edge of color jincident in uand at most one edge of color jincident in v. Case 1: Every troublesome vertex xsatisfies d∗ M(x)≥34k. 54
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES Case 1.1: There exists a non-troublesome vertex v∈Si−1with d′(v)< 34k, then •choose w∗∈ {w∈S0: (v, w)/∈B∪M}uniformly at random, add (v, w∗)to Mand color it with 0. •Set Si=Si−1and Pi=Pi−1. Case 1.2: Every non-troublesome vertex vin Si−1has a degree of d′ M(v)≥ 34k. We have two cases: Case 1.2.1: There are two elements Pand P′in some P(j) i−1that are (u, v)-available. Then: •Choose Pand P′from P(j) i−1which are (u, v)available such that P(j) i−1is minimal with respect to j. •Add {u, v}to Mand color it with j. •Set Si=Si−1and P(j) i=P(j) i−1−P−P′+P∗where P∗is the path P∗=P◦(u, v)◦P′. Case 1.2.2: Else end stage 1, move to stage 2, and set i∗ 0=i−1. Case 2: There is a troublesome vertex v∈Si−1such that d∗ M(v)<34k. Select vto be a troublesome vertex v∈Si−1such that d∗ M<34k, having maximum danger (with arbitrarily broken ties). Then we have two cases: Case 2.1: If there is no w∈V−Si−1such that (v, w)is unclaimed, set i∗ 0=iand the game ends. Case 2.1: Otherwise •choose such a wand claim (v, w)and color it with 0; •set Si=Si−1∪{w}and for each j∈[k]set Pj ito be the set obtained from Pj i−1by deleting the path Pthat contained wand adding the components of P−wand recolor all j-edges incident in vwith k+ 1. 5.2.2 Stage 2: Closing kHamilton Cycles Stage 2 will be repeated until Maker has created kedge disjoint Hamiltonian cycles. To start each iteration set l∈[k]such that l−1is the number of monochromatic Hamiltonian cycles already constructed. We call an edge of color j < l protected. These edges will no longer be recolored by our algorithm. For notational ease let Eibe the set of endpoints of paths in P(l) iand S′ i:= Si∪Ei. Let further Mi:= {e∈M:c(e)∈ {0, l}}.Now let P(l) i∗ lbe the longest path in Ml that only uses edges in Mi∗ land covers at least one vertex of S′ i∗ l.Maker builds a sequence of paths P(l) i∗ l, P(l) i∗ l+1, . . . such that V(P(l) i)⊆V(P(l) i+1)and P(l) i+1 is the longest path that uses only edges in Ml. Case 1: Every troublesome vertex xhas a degree of d∗ M(x)≥34k. Case 1.1: There is a non-troublesome vertex v∈Si−1with d′ M(v)<34k. Then 55
5.2. DESCRIBING THE ALGORITHM HAMILTON-CYCLES •choose w∗∈ {w∈S0: (v, w)/∈B∪M}uniformly at random, add (v, w∗)to Mand set c({v, w}) = 0; •set Si=Si−1and Pi=Pi−1. Case 1.2: Every non-troublesome vertex vin Si−1has a degree of d′ M(v)≥ 34k. Then Case 1.2.1: There is some endpoint v∈ Eiof an l-colored path, which satisfies d′ M(v)<34k. Then •choose w∗∈ {w∈S0: (v, w)/∈B∪M}uniformly at random, add (v, w∗)to Mand set c({v, w∗}) = j. •set Si=Si−1and Pi=Pi−1. Case 1.2.2:(Prolongation of Piusing rotations) Every v∈ Eisatisfies d′ M(v)≥34k. Case 1.2.2.1: There is no cycle of Mlwith vertex set V(Pi)but there exists a path of Miwith vertex set V(P(l) i)and endpoints u, v in S′ isuch that {u, v}is unclaimed, •add (u, v)to Mand set c({u, v}) = j; •set Si=Si−1and P(l) i=P(l) i−1. Case 1.2.2.2: Else •if there is a Hamilton cycle H⊆Ml, –for each edge eon Hset c(e) = l, protect H, set l←l+ 1, and i∗ l=i−1. –Now if l=k+ 1 end the game. Otherwise repeat stage 2 with the updated values. •Otherwise end the game reporting failure. Case 2: There is a troublesome vertex v∈Si−1such that d∗ M(v)<34k. Select vto be a troublesome vertex v∈Si−1such that d∗ Ml<34k, having maximum danger (with arbitrarily broken ties). Then Case 2.1: There is no w∈V−Si−1such that (v, w)is not in B∪M, then set i∗ 1=iand end the game. Case 2.2: Otherwise •choose such a w, add (v, w)to Mand set c({v, w}) = 0; •set Si=Si−1∪{w}and for each j∈[k]set Pj ito be the set obtained from Pj i−1by deleting the path Pthat contained wand adding the components of P−w. Remark 5.10 Let j∈[k].Note that paths in P(j)only grow if case 1.2.1 applies and two available paths are connected. Since paths are only available if both their lengths are at most log(n).Thus in each step each element of P(j)are of length at most log(n). 56
5.4. VERIFYING MAKER’S STRATEGY This requires that Maker keeps track of the edge that are already earmarked for a specific Hamilton cycle by building the P(j)as edge disjoint. This approach further requires that the Sido not lose their connectedness and expander-like properties after the edges of at most 2kedges are "protected" in each vertex. This will be achieved by increasing the Maker out-degree of vertices in Si. Assume that l∈[k]is the active color during turn i≥i∗ 0. Recall that S′ iis the union of Siand all endpoints of paths in P(l) i. Further S0⊆Vwas chosen at the beginning of the algorithm Hamilton-Cycles arbitrary with |S0|= 1000(4k+ 3)2√k+ 2n qlog(n) ≥2004n qlog(n)(5.1) For each Z⊆S′ idefine N′(Z) := {v∈Si\Z:∃u∈Zs.t., the edge (u, v)was chosen by Maker and c((u, v)) = 0}. Lemma 5.23 Consider i≥i∗such that Case 1.2.2 applies. Then with probability 1−o (1) for every set S⊆Sithat contains no troublesome vertices and that satisfies |S| ≤ |Si| 2,we have |N′(S)|>min |Si| 2−|Z|,2k+ 1 30k−1|Z|!, if at most 2kout-edges have been removed from each vertex in S. Proof. Let Z⊆Siwith |Z| ≤ |Si| 2.Note that by Corollary 5.21, and the chosen cardinality of S0, |Si| 2≤|Sf| 2≤1001 |S0| 2000 .(5.2) Case 1 : |Z| ≥ |S0| 4. Consider a vertex v∈Sand an arbitrary set of 32k0-colored out-edges incident in v. Note that these edges have been chosen in case 1.1 of either stage. This choice was made uniformly at random between all vertices w∈S0,such that (v, w)was unclaimed. Let further B⊆S0\|Z|with |B|=j|Si| 2k−Z. Let Av,i ⊆S0be the set of all vertices wsuch that {v, w}was unclaimed by either player in turn i. Since v is not troublesome, at most n √log(n)Breaker edges are incident in v. Furthermore, at most 34k≤n √log(n)Maker-edges are incident in v. This implies |Av,i| ≥ |S0|− 2n √log(n). Thus, the probability that each edge chosen from v(in some step in which Case 1.1 applied) ends in B∪Z, is at most |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 200032k (5.3) The second last inequality holds because by inequality (5.1), |S0| ≥ 2004n √log(n),and thus |S0|− 2n √log(n)≥1001|S0| 1002 . The probability that there exists a set of 2kout-edges such that the endpoints of all remaining 32kout-edges from vare all in B∪Zis at most 34k 2k!501 200032k ≤ 34ke 2k!2k501 200032k (with 5.3) ≤(17e)2k501 200032k = (17e)32k 16 501 200032k ≤3 232k501 200032k =1503 400032k Thus, the probability that the statement above is true for all vertices in Zis at most 1503 400032k|Z|, and the probability that there exist Zand Bwith the properties mentioned above is at most |Si| |Z|! |S0| |B|!1503 400032k|Z| ≤ |Si|e |Z|!|Z| |S0|e |B|!|B|1503 400032k|Z| ≤ |Si|e |Z|!|Z| 2|S0|e |S0|!|S0| 21503 400032k|Z| ≤ |Si|e |Z|!|Z|(2e)2|Z|1503 400032k|Z|(since |Z| ≥ |S0| 4) ≤(2e)|Z|(2e)2|Z|1503 400032k|Z| ≤(2e)3|Z|1503 400032k|Z| ≤5·1503 4·400032k|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. Consider a vertex v∈Sand an arbitrary set of 32k0-colored out-edges incident in v. Note that these edges have been chosen in case 1.1 of either stage. This choice was made uniformly at random between all vertices w∈S0,such that (v, w)was unclaimed. Let further B⊆S0\Zwith |B|=j2k+1 30k−1|Z|k.Let Av,i ⊆S0be the set of all vertices wsuch that {v, w}was unclaimed by either player in turn i. Since v is not troublesome, at most n √log(n)Breaker edges are incident in v. Furthermore, at most 34k≤n √log(n)Maker-edges are incident in v. This implies |Av,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 last inequality holds, because by inequality (5.1) |S0| ≥ 2000n √log(n)and thus |S0|− 2n qlog(n)≥999 1000 |S0|.(5.4) Therefore, the probability that there exists a set of 2kout-edges such that the endpoints of all remaining 32kout-edges from vall end in B∪Zis at most 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, the probability that the statement above is true for all vertices in Zis at most 3|Z| 2|S0|!32k|Z|, and the probability that there exist Zand Bwith the properties mentioned above is at most |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 definition of B) ≤ 1001e 1000 |S0| |Z| e(30k−1) 2k+ 1 !2k+1 30k |S0| |Z|!2k+1 30k−13 232k |Z| |S0|!32k |Z| ≤ 1001e 1000 |S0| |Z|(15e)2k+1 30k |S0| |Z|!2k+1 30k−13 232k |Z| |S0|!32k |Z| = 1001e 1000 (15e)2k+1 30k3 232k |S0| |Z|!2k+1 30k−1|S0| |Z| |Z| |S0|!32k |Z| = 1001e 1000 (15e)2k+1 30k3 232k |Z| |S0|!−2k+1 30k−1 |Z| |S0|!−1 |Z| |S0|!32k |Z| ≤ 1001e 1000 (15e)2k+1 30k3 232k |Z| |S0|!30k |Z| . Case 2.1 : |Z| ≥ √n, then 1001e 1000 (15e)2k+1 30k3 232k |Z| |S0|!30k |Z| ≤ 1001e 1000 (15e)2k+1 30k3 232k1 430k!|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 that by definition |S0| ≥ n √log(n),thus 1001e 1000 (15e)2k+1 30k3 232k |Z| |S0|!30k |Z| ≤ c√nqlog(n) n 30k|Z| (for some constant c > 0) ≤ cqlog(n) √n 30k|Z| = o n qlog(n) . Thus, the proof is completed by summing over all of these probabilities. For s≤j|Si| 2kdefine Asas the event that there exists a set Z⊆Siof size kthat contains no troublesome vertices and that satisfies N′(Z)≤|Si| 2−|Z|.We further define Bsas the event that there exists a set Z⊆Siof size sthat contains no troublesome vertices and that satisfies N′(Z)≤2k+1 30k−1|Z|.Now we have |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) ≤|Sf| 2·o n qlog(n) (since |Si| ≤ |Sf|) ≤1001(4k+ 3)3√k+ 2n qlog(n)·o n qlog(n) (by Corollary 5.21) = o (1) . Thus with probability 1−o (1) ,each set Z⊆Siwith |Z| ≤ Si 2satisfies |N′(Z)|> |Si| 2−|Z|,or |N′(Z)| ≤ 2k+1 30k−1|Z|and the result is proved. Lemma 5.24 With probability 1−o (1) ,for every i≥i∗in which case 1.2.2 applies and for every Z⊆Siwhich contains no troublesome vertex and for which |Z| ≤ √(k+2)n √log(n)≤|S0| 1.000(4k+3)2,we have N′(Z)>(4k+ 2)|Z|. Proof. Let Z⊆Siwith |Z| ≤ |S0| 1.000(4k+3)2such that Zdoes not contain any troublesome vertices. Let further B⊆S0\Zwith |B|= (4k+ 2)|Z|.Note that every 67
5.4. VERIFYING MAKER’S STRATEGY out-neighbor of such a non-troublesome vertex v∈Zwas chosen during case 1.1 during either stage. The neighbors of non-troublesome vertices are chosen uniformly at random from all vertices in S0that are not yet joined to v. Let A⊆S0be the set of vertices wsuch that the edge {v, w}was not claimed by neither Breaker nor Maker. Since vis non-troublesome Breaker has chosen at most n √log(n)edges that are incident in v. Furthermore, Maker has chosen at most 34k≤n √log(n)edges incident in v. This implies |A|≥|S0|− 2n √log(n) Now the probability that from a fixed vertex vthat all its 34kout-neighbors are in Z∪Bis at most |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, the probability that every out-neighbor of every vertex in Zend up in Z∪Bis at most (4k+ 3)|Z|1000 |S0|999 !34k|Z|. Thus, the probability that there exist Zand Bas above is at most |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 that |Z| ≥ √n. Then we have 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 34k1 1.00027k 1 (4k+ 3)20k(4k+ 2)(4k+2) !!|Z| ≤2−√n= o n qlog(n) . 68
5.4. VERIFYING MAKER’S STRATEGY On the other hand, if we assume that |Z|<√n, then the probability that there exist Zand Bas above is at most 1001e 1000 e (4k+ 2)!(4k+2) (4k+ 3)1000 999 !34k |Z| |S0|!27k |Z| ≤ cqlog(n) √n 27k (for some c > 0) = o n qlog(n) . For s∈[k]let Asbe the event that there exist sets Zand Bas above swith |Z|=s. Then the probability that there exists a sets Zwith |Z| ≤ √(k+2)n √log(n)and N′(Z)≤(4k+ 2)|Z|is at most P [ s≤√(k+2)n √log(n) As ≤X s≤√(k+2)n √log(n) P(As)(by the 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 proves the lemma. The next result allows us to ensure that for each i≥i∗,if case 1.2.2 applies, the graph induced by Siis connected, even if up to 2kedges have been removed from each vertex. The 2kedges that are removed in these steps represent the edges that form the kHamiltonian cycles that might already have been protected and can thus no longer be used to form other Hamilton cycles. Lemma 5.25 For every i≥i∗in which case 1.2.2 applies and for each Z⊆Si, with |Z| ≤ |Si| 2the set |N′(Z)|is non empty with probability 1−o (1) if not more than 2kedges have been removed from each vertex. This implies Siis connected if not more than 2kedges have been removed from each vertex and thus Siis (2k+ 1)- edge-connected with probability 1−o (1) . Furthermore, if |Z| ≤ √(k+2)n √log(n),then |N′(Z)|>2k|Z|with probability 1−o (1) . 69
5.4. VERIFYING MAKER’S STRATEGY Proof. Let T⊂Zbe the set of troublesome vertices in Zand S:= Z\T. Let v be a troublesome vertex. Since case 1.2.2 applies, 34kedges that are incident in v were added after vbecame troublesome. All of these edges were added in a step in which case 2.1 of either stage applied. Whenever case 2.1 of either stage applies in a round ˆı, a troublesome vertex is connected to a vertex w∈V\Sˆı.In addition the vertex wis moved into Sˆı+1.Thus wcannot be joined to another troublesome vertex during a round in which case 2.1 applies. This implies that |N′(T)|contains at least 34k|T|vertices. |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 have a "large" number of troublesome vertices in Z. Then |Z|+|N′(Z)| ≥ 32k|T|>(2k+1)|Z|.This proves the second statement of the lemma. The first statement can be obtained by subtracting |Z|from both sides of the inequality, which yields |N′(Z)|>2k|Z|>0.Thus N′(Z)=∅. Case 2 :|T| ≤ 2k+1 32k|Z|.We first have |S|=|Z|−|T|≥|Z|− 2k+ 1 32k|Z|=30k−1 32k|Z|.(5.5) Then, since Sdoes not contain any troublesome vertices and |S| ≤ |Si|/2as pbserved above, by Lemma 5.23 with probability 1−o (1) we get |N′(S)|>2k+ 1 30k−1|S|or |N′(S)|>|Si| 2−|S|.(5.6) using the assumption |Z| ≤ |Si|/2. This implies, using inequality (5.5), |Z|+|N′(Z)|≥|S|+|N′(S)|>2k+ 1 30k−1|S|+|S| ≥ 32k 30k−1|S| ≥ |Z|. or |Z|+|N′(Z)| ≥ |N′(S)|+|S|>|Si| 2≥ |Z|. By subtracting |Z|from the left-hand-sides and the right-hand-sides both inequalities imply |N′(Z)|>0and thus N′(Z)=∅. Furthermore, let us assume |Z| ≤ √(k+2)n √log(n).Then |S| ≤ √(k+2)n √log(n),and since S does not contain troublesome vertices, we can apply Lemma 5.24. So, with probability 1−o (1) we have |N′(S)|>(4k+ 1) |S|.Thus, with probability 1−o (1) we have |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|(with (5.5)) ≥(2k+ 1) |Z|. By subtracting |Z|from both sides of the inequality we get |N′(Z)|>2k|Z|. Theorem 5.26 Maker can always make a choice as required by the strategy. Furthermore, the game does not end in Case 2 of any stage. Thus stage 1 ends in Case 1.2.2. Proof. We first show that Maker can make the required choice in Case 1.1 of either stage. In Case 1.1 of either stage Maker is supposed to connect a non-troublesome vertex in Sito a vertex in S0.Recall that |S0|=1000(4k+3)2√(k+2)n √log(n).Now if vis a non-troublesome vertex with d′ M(v)<34k, then we know that Maker chose at most 34k0-colored out-edges from v, and at most 2k(k+ 1)-colored edges incident in v. Thus, there are at most 36kMaker out-edges incident in v. Since kis constant, clearly 36k < n √log(n).Furthermore, since vis non-troublesome, by definition Breaker chose at most n √log(n)edges incident in v. So, d′ M(v) + dB(v)≤36k+n qlog(n)<2n qlog(n). Hence in both stages Maker can make the desired choice in Case 1.1, since at least |S0|− 2n qlog(n)((4k+ 3)2q(k+ 2) −2) n qlog(n) vertices in S0are not incident in Maker or Breaker edges and available for Maker’s connections. In case 1.2.1 of Stage 2, Maker is required to connect an endpoint vof a path in P(l) iwith to a vertex in S0.Note that vis not in Siand thus non-troublesome. Therefore, by the same arguments as were used for the case 1.1, there are at least ((4k+ 3)2q(k+ 2) −2) n √log(b)vertices in S0that are not yet adjacent to v. To handle case 2 in each of the stages we combine Corollary 5.21 with Lemma 5.22. Maker has to connect vto some vertex in V\Si−1.If case 2 applies in any step i, there exists a troublesome vertex vwith d∗ Ml(v)<34k. By Lemma 5.22, dB(v)< n−n(4k+3)3+2k+1 √log(n).Furthermore, Maker claimed at most 2kedges incident in vthat were chosen in Case 1.2.1 of stage 1. They were (k+1)-colored in step i. In addition, Maker has chosen at most 34k0-colored edges from vbefore vbecame troublesome and at most 34k−1 0-colored edges from vafter vbecame troublesome. Thus, the 71
5.4. VERIFYING MAKER’S STRATEGY amount of Maker out-edges incident in vis at most 70k−1<70k. Since for all i≤f, Si⊆Sf,Corollary 5.21 part 1 yields |Si|≤|Sf|<((4k+ 3)2q(k+ 2)1001)n qlog(n). So let Av⊆V\Si−1be the set of vertices that can be chosen to be connected to v by Maker in step i. Then |Av| ≥ n−|Si|−dB(v)−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 constant. Thus Maker can always choose an edge in Case 2.1 and the game does not end in Case 2.2. of either step. The idea of using rotations to build Hamiltonian cycles was first introduced by Posa [Pó76]. His technique uses the following fact. Let P=v0v1. . . vxbe a path of length x≥4and y≤x−2such that {vx, vy} ∈ E. Then P+{vx, vy}−{vy, vy+1} is a path of length xand endpoints vy+1 and v. However, the type of rotations that are helpful in our context is limited. Definition 5.27 Let P=vv1. . . vxbe a path with both endpoints in S′ i,and y≤x−2such that {vx, vy} ∈ Mlwith vx∈e. Then we call P′=P+ {vx, vy}−{vy, vy+1}a limited v-Ml-rotation from P. We call a path P′′ constructible from Pby repeated limited v-Ml-rotations from P, if there exists a series of limited v-Ml-rotations P,...,P′′, such that the end-result is P′′. v vy vx−1 vx Figure 5.5: Here we depict a limited v-Ml-rotation with the same notation as in Definition 5.27, obtaining P′from P. This technique allows us to construct a family of paths with the same vertex set and length as P(l) i.By showing that this family is large we will prove that Maker will always be able to close a cycle on the vertices of P(l) i.We begin by showing that at least one of these paths has both of its endpoints in S′ i. 72
5.6. ANALYZING THE DURATION OF STAGE 3 Case 1.2.2: If there exists a v∈Ai−1,but no w∈Ai−1such that Case 1.2.1 would be satisfied, choose w′∈S0,such that {v, w′} /∈M∪B. Then add {v, w},set c({v, w}) = k, Ci=Ci−1, Ai=Ai−1\{v}and Bi=Bi−1∪{v}. Case 1.2.3: Otherwise Ai−1=∅and we end the game. Case 2: There is a troublesome vertex w∈Ci−1such that d∗ M(v)<34k. Select vto be a troublesome vertex v∈Ci−1such that d∗ M(v)<34k, having maximum danger dang(v) := dB(v)−bd∗ M(v)(with ties arbitrarily broken ). Then Case 2.1: If there is no w′∈V−Ci−1such that (v, w′)is not in B∪M, end the game. Case 2.2: Otherwise, –choose such a w′and add (v, w′)to M. Color (v, w′)with color 0,so c(v, w∗) = 0. –Set Ci=Ci−1∪{w′}and for each j∈[k]set Pj ito be the set obtained from Pj i−1by deleting the path Pthat contained w′and adding the components of P−w′. 5.6 Analyzing the duration of Stage 3 To analyze the additional stage of the algorithm we recall the following definitions. fis the number of turns carried out in Stage 1 and Stage 2, and tis the number of troublesome vertices at the end of the game. Further, let f2be the number of turns played in Stage 1, Stage 2 and Stage 3. By Theorem 5.7 at most k∗n+On √log(n)=(k−1)n 2turns have been carried out. We now estimate the number of turns that were carried out in Stage 3. Lemma 5.33 The number of turns in which Case 2 of either Stage applies can be estimated to be at most 34 ·k∗·t. Proof. The proof is analogous to the proof of Lemma 5.11. Whenever Case 2 applies in any step of either stage, edges are added to a troublesome vertex vwith d∗ M(v)<34k∗.We add one edge per turn, thus, the number of turns spent on each troublesome vertex is 34k∗.Since there are ttroublesome vertices at the end of the algorithm, the number of rounds spent in these cases is at most 34k∗t. Lemma 5.34 The number of turns taken in Case 1.1 of either Stage applies can be estimated to be at most 34 ·k∗·|Cf2|. Proof. The proof is analogous to the proof of Lemma 5.12. Whenever Case 1.1 of either stage every troublesome vertex vsatisfies d∗ M(v) = 34k. Note that for each i1≤f, Si1⊆Sf=C0.Furthermore, for each i2≤f2we have Ci2⊆Cf2.Thus, for each non-troublesome vertex v∈Cf2we increase d′ M(v) 79
5.6. ANALYZING THE DURATION OF STAGE 3 to 34k, adding one edge per turn. In the worst case all vertices in Cf2are nontroublesome and have to be increased in these steps. Thus, the number of turns is at most 34k·|Cf2|. Lemma 5.35 The number of turns in which Case 1.2.1 of Stage 3 applies, can be estimated to be at most |A0| 2≤n 2. Proof. Since A0⊆V, we have |A0|≤|V| ≤ n. If Case 1.2.1 of Stage 3 applies, there is a pair of vertices v, w ∈Ai−1⊆A0in different path components of P(k∗) f. Since both v, w are then removed from |Ai−1|,it takes at most |A0| 2≤n 2such steps to remove every vertex from A0. Lemma 5.36 The number of turns in which Case 1.2.1 of Stage 3 applies can be estimated to be at most 2n √log(n). Proof. We show that for each i≤f2so that in step iCase 1.2.1 of Stage 3 applies, we have |Ai−1|<2n √log(n).Whenever Case 1.2.1 of Stage 3 applies, Maker reduces the size of Ai−1by one. So at most 2n √log(n)such steps are needed until Ai−1is empty. If Case 1.2.2 of Stage 3 is carried out, Case 1.2.1 of Stage 3 does not apply. Thus, there exists no pair of vertices v, w ∈Ai−1,such that [v](k∗) f= [w](k∗) fand {v, w}is unclaimed. Now consider an arbitrary v∈Ai−1.Since there is no w∈Ai−1such that [v](k∗) f= [w](k∗) fand {v, w}is unclaimed, each w∈Ai−1\{v}must fulfill one of the following two properties. Either wis in [v](k∗) f,or {v, w}has been claimed by a player. Thus |Ai| ≤ dB(v) + dM(v) + |[v](k∗) f|. Observe that |[v](k∗) f| ≤ 2 log(n)<n 2√log(n)by Remark 5.10. Now we bound the number of w∈Ai−1\{v}such that {v, w}has been claimed by a player. Since vis in Ai−1,it is not in Ci−1and is non-troublesome, so by definition dB(v)<n √log(n).Furthermore, since vis an interior vertex of [v](j) ffor any j∈[k∗],exactly 2k∗Maker edges incident in vhave been added. As k∗is constant and nis assumed to be large enough, dM(v)=2k∗≤n 2√log(n). We conclude |Ai| ≤ dB(v) + dM(v) + |[v](k∗) f| ≤ n qlog(n). We now can give a preliminary upper bound on the number of turns that are carried out during Stages 1, 2 and 3. Note that we count the number of turns carried out in case 2 and case 1.1 double. This will turn out to be not problematic, because the number of steps carried out in these steps is On √log(n). 80
5.6. ANALYZING THE DURATION OF STAGE 3 Lemma 5.37 The number of turns carried out in Stages 1, 2 and 3 in total is at most (2k∗+ 1)n 2+ 34k∗·t+ 34k∗·|Cf2|+O n qlog(n) ≤70k∗·n. Proof. This result is analogous to the proof ofLemma 5.16. By the lemmata 5.33 through 5.36 and Lemma 5.20 the number of moves played in Stages 1, 2 and 3 combined is at most 34k∗·t | {z } Lemma 5.33 + 34k∗·|Cf2| | {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∗·t+ 34k∗·|Cf2| | {z } ≤68k∗n +O n qlog(n) ≤70k∗·n, using the trivial upper bound nfor |Cf2|and t. Lemma 5.38 The number of troublesome vertices after Stages 1, 2 and 3 are completed is at most t≤140k∗n qlog(n). Proof. This proof is analogous to the proof of Lemma 5.17. By Lemma 5.37 the game lasts for at most 70k∗nturns. Since Breaker claims b≤n log(n)edges in each turn, we have |B| ≤ 70 ·k∗·n·b≤70k∗n2 log(n). Furthermore, each troublesome vertex has Breaker degree at least n √log(n).In addition each Breaker edge is incident in at most two troublesome vertices. Thus t≤2·|B|· qlog(n) n≤2·70 ·k∗n qlog(n). Lemma 5.39 At the end of the game we have |Cf2| ≤|S0|+ 35k∗t ≤1000(4k∗+ 3)2√k∗+ 2n qlog(n)+ 35k∗t ≤1000(4k∗+ 3)2√k∗+ 2n qlog(n)+ 4900k∗n qlog(n). 81
5.6. ANALYZING THE DURATION OF STAGE 3 Proof. This proof is analogous to the proof of Lemma 5.18. If at the end of Stage 3 a vertex vis in Cf2,it arrived there by one of the following three ways: a) it was in S0,b) it became troublesome over the cause of the game (which implies it was added between steps) and c) it is one of the 34k∗ out-neighbors of a troublesome vertex during case 1.1. of either Stage. Thus for each troublesome vertex at most 35k∗vertices end up in Cf2,and at most 35k∗t vertices satisfy possibility b) or c). Obviously, there are |S0|vertices which satisfy possibility a). The second inequality follows from the definition of S0and the third inequality is true by Lemma 5.38. Now that we have given a rough upper bound on the number of rounds played, it is time to refine our result with the new upper bounds for tand |Cf2|. Lemma 5.40 At most kn 2+On √log(n)turns have been carried out in Stages 1, 2 and 3. Proof. By Lemma 5.37 the game ends after (2k∗+ 1)n 2+ 34k∗·t+ 34k∗·|Cf2|+O n qlog(n) turns. By Lemma 5.38, t∈ On √log(n)and by Lemma 5.39, |Cf2| ∈ On √log(n). Thus, the number of turns that were carried out by Maker is at most (2k∗+ 1)n 2+O n qlog(n) =k·n 2+O n qlog(n) . Since the game lasts for at most k·n 2+On √log(n)turns and Breaker claims b≤n log(n)edges in each turn, |B| ≤ k·n 2+O n qlog(n) ·b≤(k+ 1)n2 2 log(n). Each troublesome vertex has Breaker degree at least n √log(n).In addition, each Breaker edge is incident in at most two troublesome vertices. Thus t≤2·|B|· qlog(n) n≤2·k+ 1 2 n qlog(n)≤(k+ 1) ·n qlog(n). Corollary 5.41 At the end of the game we have t≤(k+ 1) n qlog(n)and |Cf2|≤|S0|+ 35(k+ 1)k∗qlog(n). 82
5.7. PROVING THE k-EDGE-CONNECTIVITY OF MAKER’S GRAPH Proof. Each troublesome vertex has Breaker degree at least n √log(n).In addition each Breaker edge is incident in at most two troublesome vertices. Thus t≤2·|B|· qlog(n) n≤2·k+ 1 2 n qlog(n)≤(k+ 1) ·n qlog(n). By Lemma 5.39 we have |Cf2|≤|S0|+ 35k∗t≤ |S0|+ 35(k+ 1)k∗qlog(n). 5.7 Proving the k-Edge-Connectivity of Maker’s Graph We already established that the game ends after at most kn 2+On √log(n)turns. We now have to show that the Maker graph is k-edge connected after stages 1, 2 and 3 have been carried out. We begin by showing that the algorithm is well-defined, i.e. that the choices that it requires can be made in any given step. Of course, this is true for every step during stages 1 and 2. Thus we will only consider the steps taken during Stage 3. Lemma 5.42 Maker can always make the moves required by the algorithm k-edgeconnectivity (during Step 3). Proof. We consider the cases of Stage 3. We first observe that Maker can make the move required by the algorithm when Case 1.2.1 applies, since this case applies only when the edge Maker is supposed to choose exists and is unclaimed. The arguments that Maker can make the required choice in Case 1.1 and Case 1.2.2 are similar and can be handled together. In both of these cases Maker has to connect a non-troublesome vertex vto a vertex w∈S0.Note that vin Case 1.1 is explicitly non-troublesome, while in Case 1.2.2 vis in Ai−1.Since all troublesome vertices in step iare in Ci, v is non-troublesome when Case 1.2.2 applies. Thus, dB(v)≤n √log(n).Furthermore, Case 1.1 requires d′ M(v)<34k < n √log(n)and Case 1.2.2 applies to a vertex of Ai−1.So, if Case 1.2.2 applies, vis an interior vertex of [v](j) ffor each j∈[k∗].These vertices are not incident in Maker edges with an endpoint in Ci−1⊇S0by construction. Thus, there exist at least |S0| − dB(v)− d′ M(v)≥ |S0|− 2n √log(n)vertices w∗∈S0such that (v, w∗)is unclaimed if Case 1.1 or Case 1.2.2 of Stage 3 apply. Now we want to show that Maker can make the required choice in Case 2 of Stage 3. So, let i≤f2such that Case 2 of Stage 3 applies. Let v∈Ci−1be a troublesome vertex with d∗ M(v)≤34k∗and maximum danger. By Lemma 5.22, dB(v)≤n− (4k+3)3n+2k+1 √log(n).Furthermore, vwas non-troublesome when Stage 3 started, otherwise 83
5.7. PROVING THE k-EDGE-CONNECTIVITY OF MAKER’S GRAPH Stage 2 would not have concluded. The number of edges present in vat the start of Stage 3 that end in V\Cfand were of some color j∈[k∗]when vwas moved to Cfis at most 2k∗≤n √log(n).In conclusion, there exist at least |V\Ci−1|−2k∗−dB(v) ≥|V|−|Ci−1|−2k∗−dB(v) ≥n−|Cf2|− n qlog(n)−n+(4k+ 3)3n+ 2k+ 1 qlog(n) ≥(4k+ 3)3n2k+ 1 qlog(n)−n qlog(n)−|Cf2|(by Corollary 5.41) vertices w∗∈V\Ci−1such that {v, w∗}is unclaimed. Proof of Theorem 5.9. If kis even Maker builds k∗=⌊k 2⌋Hamilton cycles with the algorithm Hamilton-Cycles. By Menger’s theorem the constructed graph is k-edgeconnected and we are done. So, let k∈N≥3be odd. Note that 2k∗+ 1 = k. Now, by Lemma 5.25 and since 2k∗+ 1 = k, C0is k-edge connected with probability 1−o (1) . We assume for a moment that there exists a set ˆ Eof k−1edges such that M\ˆ E is not connected. Then there exists v∈Vnot belonging to the same (M\ˆ E)- component as C0. Since for each color j∈[k]there exist two j-colored paths in Mconnecting v and C0,ˆ Ehas to contain two edges of each color from Mand both have to be in [v](k∗) f.Otherwise, there is a path remaining from vto some vertex of C0. v C0 Figure 5.11: An example of a situation where vis an inner vertex of a red-colored path and a blue-colored path i.e. k∗= 2, implying 4=2k∗edges (two red, two blue) have to be removed to disconnect vfrom C0. 84
5.8. CONCLUSION AND OPEN QUESTIONS If vis in V\C0,it has to be in Bf2,since at the end of the game Af2is empty. If vends up to be in Bf,there are two cases. Case 1: There exists a w∈S0⊆C0such that {v, w} ∈ Mand c({v, w}) = k and this edge was added in Case 1.2.2 of Stage 3. Since c({v, w}) = k, and all edges in ˆ Eare colored with a color in [k∗],{v, w}/∈ˆ E. Thus, vis in the same (M\ˆ E)- component as C0,which is a contradiction to the assumption that vand C0are in different (M\ˆ E)-components. Case 2: There exists a w∈Bwith [v](k∗) f= [v](k∗) fsuch that {v, w} ∈ Mand c({v, w}) = k. Since ˆ Econtains only two k∗-colored edges, both of which connect vertices in [v](k∗) f,no edges have been removed from [w](k∗) f.So, in M\ˆ E, there exists an edge from S0to an endpoint uof [w](k∗) f,which was chosen in Case 1.2.1 of Stage 2. Then there exists a sub-path of [w](k∗) fconnecting uto wand finally the edge {v, w}in M\ˆ E. Because S0⊆C0, v is in the same (M\ˆ E)-component as C0.This is again a contradiction to the assumption that vand C0are in different (M\ˆ E)-components. This concludes the proof. 5.8 Conclusion and Open Questions In this chapter we managed to generalize an approach of Brüstle et al. [BCN+23] to show that for each k≥2Maker can win the 1 : n log(n)−Cn log(n)3/2Maker-Breaker k-edge-connectivity game in at most k 2n+ o (n)turns. This is also the optimal number of rounds up to the o (n)term and improves the formerly known bound by a factor of more than 8.We also used this strategy to show that Maker wins the 1 : n log(n)−Cn log(n)3/2Maker-Breaker k-factor game in lk 2mn+ o (n)rounds for each k≥2.Since Maker needs at least k 2nrounds to win the k-factor game, the only possibility to improve this result up to the o (n)term is to reduce the number of turns by n 2if kis odd. We pose the following natural questions: Question 1 : Can the approach described in this chapter be used to show that Maker wins the 1 : n log(n)−Cn log(n)3/2k-vertex-connectivity game in at most k 2n+ o (n)turns? Question 2 : Is it possible to modify the approach in such a way that it yields a Maker win in the 1 : n log(n)−Cn log(n)3/2k-factor game using at most k 2n+ o (n)if kis odd? 85
Bibliography [AKS99] Noga Alon, Michael Krivelevich, and Benny Sudakov. Coloring Graphs with Sparse Neighborhoods. Journal of Combinatorial Theory, Series B, 77(1):73–82, 1999. [Alo92] Noga Alon. Choice Numbers of Graphs: a Probabilistic Approach. Combinatorics, Probability and Computing, 1(2):107–114, June 1992. [Alo93] Noga Alon. Restricted colorings of graphs. In K. Walker, editor, Surveys in Combinatorics, 1993, pages 1–34. Cambridge University Press, 1. edition, July 1993. [AS10] Noga Alon and Benny Sudakov. Increasing the chromatic number of a random graph. Journal of Combinatorics, 1(4):345–356, 2010. [BCN+23] Noah Brüstle, Sarah Clusiau, Vishnu V. Narayan, Ndiamé Ndiaye, Bruce Reed, and Ben Seamone. The speed and threshold of the biased perfect matching and Hamilton cycle games. Discrete Applied Mathematics, 332:23–40, June 2023. [BE76] B. Bollobas and P. Erdös. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 80(3):419–427, November 1976. [BFM03] Tom Bohman, Alan Frieze, and Ryan Martin. How many random edges make a dense graph hamiltonian? Random Structures & Algorithms, 22(1):33–42, 2003. [BMPP20] Julia Böttcher, Richard Montgomery, Olaf Parczyk, and Yury Person. EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS. Mathematika, 66(2):422–447, April 2020. [Bol85] Béla Bollobás. Random graphs. Academic Pres, London, 1985. [Bol88] Béla Bollobás. The chromatic number of random graphs. Combinatorica, (8), 1988. [Bol98] Béla Bollobás. Modern Graph Theory, volume 184 of Graduate Texts in Mathematics. Springer New York, New York, NY, 1998. 86
BIBLIOGRAPHY [BPSS23] Julia Böttcher, Olaf Parczyk, Amedeo Sgueglia, and Jozef Skokan. Triangles in randomly perturbed graphs. Combinatorics, Probability and Computing, 32(1):91–121, January 2023. [CE78] V. Chvátal and P. Erdös. Biased Positional Games. In Annals of Discrete Mathematics, volume 2, pages 221–229. Elsevier, 1978. [CHMP20] Dennis Clemens, Fabian Hamann, Yannick Mogge, and Olaf Parczyk. Positional games on randomly perturbed graphs. arXiv:2009.14583 [math], September 2020. arXiv: 2009.14583. [Die17] Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, fifth edition edition, 2017. [DMT19] Shagnik Das, Patrick Morris, and Andrew Treglown. Vertex Ramsey properties of randomly perturbed graphs. arXiv:1910.00136 [math], September 2019. arXiv: 1910.00136. [DRRS20] Andrzej Dudek, Christian Reiher, Andrzej Ruciński, and Mathias Schacht. Powers of Hamiltonian cycles in randomly augmented graphs. Random Structures & Algorithms, 56(1):122–141, January 2020. [ER59] P. Erdős and A. Rényi. On Random Graphs. Publicationes Mathematicae, 6:pp 290–297, 1959. [ERT79] P. Erdős, A. L. Rubin, and H. Taylor. Choosability in graphs. Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, XXVI:125–157, 1979. [FK16] Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, Cambridge, 2016. [Gil59] E. N. Gilbert. Random Graphs. The Annals of Mathematical Statistics, 30(4):1141–1144, December 1959. [GS09] Heidi Gebauer and Tibor Szabó. Asymptotic random graph intuition for the biased connectivity game. Random Structures & Algorithms, 35(4):431–443, December 2009. [HKSS14] Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó. Positional Games, volume 44 of Oberwolfach Seminars. Springer Basel, Basel, 2014. [HR21] Annika Heckel and Oliver Riordan. How does the chromatic number of a random graph vary? 2021. Publisher: arXiv Version Number: 2. [Kri00] Michael Krivelevich. The Choice Number of Dense Random Graphs. Combinatorics, Probability and Computing, 9(1):19–26, January 2000. [Kri10] Michael Krivelevich. The critical bias for the Hamiltonicity game is (1+o(1))n/ln(n). Journal of the American Mathematical Society, 24(1):125–131, August 2010. 87
BIBLIOGRAPHY [KSvVW03] Michael Krivelevich, Benny Sudakov, H. van Vu, and Nicholas C. Wormald. On the probability of independent sets in random graphs. Random Structures and Algorithms, 22(1):1–14, 2003. [Mat70] D. Matula. The largest clique size in a random graph. Southern Methodist University. Proc. of the Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, pages 356–369, 1970. [McD89] Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, 1989, pages 148–188. Cambridge University Press, 1. edition, August 1989. [Men27] Karl Menger. Zur allgemeinen Kurventheorie. Fundamenta Mathematicae, 10:96–115, 1927. [Pó76] L. Pósa. Hamiltonian circuits in random graphs. Discrete Mathematics, 14(4):359–364, 1976. [SS87] Eli Shamir and Joel Spencer. Sharp concentration of the chromatic number on random graphs Gnp. Combinatorica, 7(1):121–129, March 1987. [Łu91] Tomasz Łuczak. The chromatic number of random graphs. Combinatorica, 11(1):45–54, March 1991. 88