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.

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

IS - Suppl 1

ER -