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, November 20, 2014, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Gal Kronenberg (Tel Aviv University)
Let P be a monotone increasing graph property. The (m:b) Maker-Breaker game is played on the edge set of Kn, in every round Breaker claims b edges and then Maker claims m edges. The game ends when all edges have been claimed. Maker wins if the graph claimed by him satisfies the property P. Otherwise, Breaker is the winner of the game.
In the (1: b) Maker-Breaker game, a primary question is to find the maximal value of b such that Maker wins by playing according to his best strategy (the so called critical bias b*). Erdos suggested the following guess which has become known as the probabilistic intuition. Consider the (1:b) Maker-Breaker game on Kn. Then the critical bias b* is the same as the maximal value of b for which Maker typically wins if both players play randomly. Therefore, a natural question to ask is how the critical bias changes when only one player plays randomly.
A random-player Maker-Breaker game is a two-player game, played the same as an ordinary Maker-Breaker game, except that one player plays according to his best strategy and claims one element in each round, while the other plays randomly and claims b elements. In fact, for every (ordinary) Maker-Breaker game, there are two different random-player versions: the (1:b) random-Breaker game and the (b:1) random-Maker game. In this talk, we analyze the random-player version of several classical Maker-Breaker games such as the Hamilton cycle game, the perfect matching game and the k-vertex-connectivity game. For each of these games we find or estimate the asymptotic values of b that allow each player to typically win the game. We also provide an explicit winning strategy for the "smart" player for the corresponding values of b. Joint work with Michael Krivelevich.
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