Component Games on Random Graphs

Rani Hod*, Michael Krivelevich, Tobias Müller, Alon Naor, Nicholas Wormald

*Corresponding author voor dit werk

OnderzoeksoutputAcademicpeer review

47 Downloads (Pure)

Samenvatting

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 c<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.

Originele taal-2English
Pagina's (van-tot)1189-1229
Aantal pagina's41
TijdschriftCombinatorica
Volume42
DOI's
StatusPublished - dec.-2022

Vingerafdruk

Duik in de onderzoeksthema's van 'Component Games on Random Graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit