TY - JOUR
T1 - Component Games on Random Graphs
AU - Hod, Rani
AU - Krivelevich, Michael
AU - Müller, Tobias
AU - Naor, Alon
AU - Wormald, Nicholas
N1 - Funding Information:
Research supported in part by USA-Israel BSF grant 2018267, and by ISF grant 1261/17.
Funding Information:
Research partially supported by NWO grants 639.031.829, 639.032.529 and 612.001.409.
Funding Information:
Research supported by Len Blavatnik and the Blavatnik Family foundation.
Publisher Copyright:
© 2022, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.
PY - 2022/12
Y1 - 2022/12
N2 - In the (1:b) component game played on a graph G, two players, Maker and Breaker, alternately claim 1 and b previously unclaimed edges of G, respectively. Maker’s aim is to maximise the size of a largest connected component in her graph, while Breaker is trying to minimise it. We show that the outcome of the game on the binomial random graph is strongly correlated with the appearance of a nonempty (b +2)-core in the graph. For any integer k, the k-core of a graph is its largest subgraph of minimum degree at least k. Pittel, Spencer and Wormald showed in 1996 that for any k ≥ 3 there exists a constant ck, which they determine, such that p = ck/n is the threshold function for the appearance of the k-core in G∼ G(n, p). More precisely, G∼ G(n, c/ n) has WHP a linear-size k-core for constant c>ck, and an empty k-core when ck. We show that for any positive constant integer b, when playing the (1:b) component game on G∼ G(n, c/ n) , Maker can WHP build a linear-size component if c > cb+2, while Breaker can WHP prevent Maker from building larger than polylogarithmic-size components if c< cb+2. For the strategy of Maker when c> cb+2, we utilise known results on the k-core. For Breaker when c< cb+2, we make use of a result of Achlioptas and Molloy (sketching its proof) that states that after deleting all vertices of degree less than k, and repeating this step a constant number of times, G is WHP shattered into pieces of polylogarithmic size.
AB - In the (1:b) component game played on a graph G, two players, Maker and Breaker, alternately claim 1 and b previously unclaimed edges of G, respectively. Maker’s aim is to maximise the size of a largest connected component in her graph, while Breaker is trying to minimise it. We show that the outcome of the game on the binomial random graph is strongly correlated with the appearance of a nonempty (b +2)-core in the graph. For any integer k, the k-core of a graph is its largest subgraph of minimum degree at least k. Pittel, Spencer and Wormald showed in 1996 that for any k ≥ 3 there exists a constant ck, which they determine, such that p = ck/n is the threshold function for the appearance of the k-core in G∼ G(n, p). More precisely, G∼ G(n, c/ n) has WHP a linear-size k-core for constant c>ck, and an empty k-core when ck. We show that for any positive constant integer b, when playing the (1:b) component game on G∼ G(n, c/ n) , Maker can WHP build a linear-size component if c > cb+2, while Breaker can WHP prevent Maker from building larger than polylogarithmic-size components if c< cb+2. For the strategy of Maker when c> cb+2, we utilise known results on the k-core. For Breaker when c< cb+2, we make use of a result of Achlioptas and Molloy (sketching its proof) that states that after deleting all vertices of degree less than k, and repeating this step a constant number of times, G is WHP shattered into pieces of polylogarithmic size.
UR - http://www.scopus.com/inward/record.url?scp=85138539782&partnerID=8YFLogxK
U2 - 10.1007/s00493-022-5036-9
DO - 10.1007/s00493-022-5036-9
M3 - Article
AN - SCOPUS:85138539782
SN - 0209-9683
VL - 42
SP - 1189
EP - 1229
JO - Combinatorica
JF - Combinatorica
ER -