Positional games

Milos Stojakovic, Department of Mathematics and Informatics, University of Novi Sad, Serbia

The theory of positional games is a fairly independent branch of combinatorial game theory, nested between theoretical computer science and mathematics. It deals with a special class of two-player perfect-information games, ranging from popular games such as Tic-Tac-Toe and Hex to some purely abstract games played on graphs. Though a close relative of the classical game theory of von Neumann and the Nim-like game theory popularized by Conway, positional games still preserve a unique flavor.

In recent years this young field has witnessed an explosion of impressive results, fresh ideas and interesting problems, and our goal is to present some of them. The course will be self-contained, assuming only the basic knowledge of combinatorics and graph theory on undergraduate level. The new concepts will be presented gradually, through examples. We start by introducing positional games, with the several standard versions of the rules. As we go along, we tackle more advanced problems, using an eclectic mix of techniques and methods originating from combinatorial game theory, extremal graph/set theory, Ramsey theory, probabilistic methods, etc.

• Positional games, examples. Different sets of rules. Tic-Tac-Toe, generalizations. Hex.
• Strong games, pairing draw. Maker-Breaker games. Biased games, threshold bias. General tools.
• Standard games on graphs – Connectivity game, Degree game, Hamilton Cycle game. Games with non-spanning winning sets, Clique game, Planarity game, Colorability game.
  
• Avoider-Enforcer games, two variants of rules, threshold biases. Standard games on graphs.
  
• Winning fast, implications in strong games.
  
• Games on sparse graphs, variations. Games on random boards.
  
• Neighborhood conjecture and related problems.
  

El curso se dictará en inglés y la evaluación consiste de un examen con modalidad take-home. Para tomar el curso es necesario tener conocimientos elementales de teoría de grafos.

Acerca del profesor

Miloš Stojaković received his PhD in Computer Science at the Swiss Federal Institute of Technology (ETH), Zurich in 2005. He currently holds the position of Associate Professor at the University of Novi Sad, Serbia. His scientific interests include positional games, discrete and computational geometry, discrete random structures, combinatorial algorithms and graph theory.