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.