• Calendar

May 29, Tuesday
11:00 – 12:00

In this talk we consider weak and strong games played on the edge set of the complete graph $K_n$. Given a graph $G=(V,E)$ and a graph property P, in the weak game $P$ two players, called Maker and Breaker, alternately claim edges from $E$. Maker wins the game as soon as the graph spanned by his edges possesses the property P. If by the time all the edges have been claimed Maker does not win, then the game ends in a draw. In the strong game $P$ two players, called Red and Blue, alternately claim edges from $E$. The winner is the FIRST player whose graph possesses $P$. We consider the $k$-vertex-connectivity game, played on the edge set of $K_n$. We first study the weak version of this game and prove that, for any positive integer $k$ and sufficiently large $n$, Maker has a strategy for winning this game within $lfloor k n/2 rfloor + 1$ moves which is clearly best possible. This answers a question of Hefetz, Krivelevich, Stojakovich and Szabo. We then consider the strong $k$-vertex-connectivity game. For every positive integer $k$ and sufficiently large $n$, we describe an explicit first player's winning strategy for this game. this is a joint work with Dan Hefetz.