Combinatorics Seminar
When: Sunday January 21, 10am
Where: Schreiber 309
Speaker: Adva Mond, Tel Aviv University
Title: Positional games on vertex sets of random graphs
Abstract:
We consider the (1:b) Maker-Breaker H-game on the vertex set of a graph G,
where H is a fixed graph and b≥1. In this game Maker and Breaker
alternately claim vertices of G, where in each turn Breaker claims b vertices
and Maker claims 1. Maker wins if in the end of the game the vertices he
claimed span a copy of H. We study the (1:b) Maker-Breaker H-game played
on the vertex set of the random graph G~G(n,p), and focus on the cases
H=C_k and H=K_k. For each of these cases we establish the asymptotic order
of the minimum value of p for which Maker typically wins the game. It turns
out, similarly to the result about the edge-version of the same question,
that the (1:1) triangle-game behaves differently from all other (1:b)
H-games where H=Ck or H=Kk and b≥1. In fact, in the triangle-game we
prove a hitting-time result.
Joint work with Gal Kronenberg and Alon Naor.