Combinatorics Seminar
When: Sunday, November 26, 10am
Where: Schreiber 309
Speaker: Alon Naor, Tel Aviv University
Title: Component games on random graphs
Abstract:
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.