The interaction of randomness and positional games with potential applications in Combinatorics and Theoretical Computer Science

• Applicant: Professor Dr. Tibor Szabó
• Subject Area: Mathematics
• Term: from 2011 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 190166904

The theory of positional games can be considered as a branch of Extremal Combinatorics. Its aim is to provide a mathematical foundation for a large variety of two player perfect information games, ranging from popular recreational games, such as HEX and Tic-Tac-Toe, to purely abstract games played on graphs and hypergraphs. Motivation for studying these games partially comes from their relevance to Computer Science and Algorithms. In recent years it has become increasingly evident that positional games are tightly related to randomization, and probabilistic intuition is an indispensable tool in their analysis. In the opposite direction, research in positional games has proven to be influential in the study of extremal and probabilistic combinatorics, satisfiability of Boolean formulas, and derandomization of algorithms. The goal of this project is to study a variety of game types aiming both to understand the relations between different games, to deepen our knowledge of concrete games and discover further applications in computer science. For our investigation it will be of crucial importance to develop the surprising, yet deep and extremely fruitful connection between positional games and randomness.

• DFG Programme: Research Grants