Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**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)

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: 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