Contact | A-Z

Thursday, May 17, 2018 - 17:15 in V2-210/216

Randomness in Positional Games

A talk in the Mathematisches Kolloquium series by
Tibor Szabó from FU Berlin

Abstract: Positional games are certain two player games of perfect information with no chance moves. Many well-known recreational games fall into this category, for example Tic-tac-toe, Hex, and Gomoku. Since the players of a positional game have a fully deterministic optimal strategy, there seems to be not much room for randomness. Nevertheless, randomness does play an integral role in the theory. Often it is the only known way to prove the $existence$ of a winning strategy and sometimes it is instrumental in $predicting$ the outcome of a game. In the talk we will concentrate on the family of Maker-Breaker games on hypergraphs, which is long known to be an extremely fertile ground for motivating applications, as well as a catalyst of fundamental concepts in Combinatorics and Theoretical Computer Science. We will demonstrate various appearances of randomness by surveying the classics and discussing the more recent developments.


© 2017–2018 Sonderforschungbereich 1283 | Privacy Policy