Combinatorics Seminar

When: Sunday, November 26, 10am
Where: Schreiber 309
Speaker: Alon Naor, Tel Aviv University
Title: Component games on random graphs


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 maximize the size of the largest connected component in his graph, while Breaker is trying to minimize it. We show that when playing the game on a random graph G, the outcome of the game is strongly correlated with the existence of a (b+2)-core in G.

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 such that p = ck/n is the threshold function for the appearance of the k-core in G~G(n,p). More precisely, WHP G(n,c/n) has a linear sized k-core when c>ck, and an empty k-core when c<ck.

We show that for any positive integer b, the random graph G~G(n,c/n) is WHP such that when playing the (1:b) component game on the edge set of G, Maker can build a linear sized component if c>cb+2, while Breaker can ensure that Maker's largest component is of polylogarithmic size if c<cb+2.

Joint work with Rani Hod, Michael Krivelevich, Tobias Müller and Nick Wormald.