## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, May 06, 2010, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Sonny Ben-Shimon (Tel-Aviv University)

## Hamiltonicity Maker-Breaker Games on Random Regular Graphs

Let G be a graph and consider the following game played by two players. The board of the game is the edge set of the graph G, and the two players take alternating turns in occupying a previously unselected edge. The game ends when all edges have been selected by the players. The goal of the first player, who we will call Maker, is to have selected by the end of the game a subset of edges which spans a Hamilton cycle in G, and the goal of the second player, who we will call Breaker, is to prevent Maker from winning (there are no draws). So, given a graph G, who wins? Although the above is described in game-theoretic terms, the focus here is purely combinatorial, namely, given a graph G proving that it possesses (or does not possess) the property that (a computationally unlimited) Maker has the ability to win the game no matter how (a computationally unlimited) Breaker chooses his strategy to prevent Maker from doing so.

Chv\'{a}tal and Erd\H{o}s who were the first to address this problem over thirty years ago showed that for large enough n the complete graph on n vertices is a win for Maker. Then, how sparse can G be and still be a win for Maker? It turns out that even if d is a fixed but large enough constant the vast majority of d-regular graphs are indeed a win for Maker, thus providing a very natural family of sparse graphs that possesses this property.

Based on joint work with Michael Krivelevich and Benny Sudakov.

Information for students and suggested topics for student talks