Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

Duration: This information is not available in the database

Location: OAT S15/S16/S17

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login