Positional Games und deren Zusammenspiel mit der Theorie von Zufallsgraphen


Project Acronym
Zufallsgraphen
 
Project Title
Positional games and their interconnection with Random Graph Theory
 
Funding Code
CL 903/1-1
 
Institute
 
Principal Investigator
 
Status
Laufend
 
Duration
01-10-2021
-
30-09-2023
 
GEPRIS-ID
 
 
Project Abstract
Positional games are an instance of perfect-information games between two players, and research on such games lies in the intersection of Extremal Combinatorics, Ramsey Theory and Random Graph Theory. Next to ad-hoc and algorithmic arguments, the methods in Positional Games Theory reach from potential function arguments over randomized strategies and derandomization to probabilistic intuition. In particular, research of the last two decades has proven very strong interconnections between extremal results on positional games and random graphs. Questions on games have thus stimulated research in Random Graph Theory, and vice versa. Under this and further aspects, various types of positional games have been studied in the last years with the so-called Maker-Breaker games being the most famous and best studied ones. While recent research gave rise to many intriguing connections between general Maker-Breaker games and properties of random graphs, such as containment or robustness properties, far less is known for other types of positional games. Therefore, one of the central goals in recent research is to examine how far and under which conditions the known interconnections can be carried over to these other game types and how these types are related to each other in general. The goal of our work programme is to expand the general knowledge on various variants of positional games with an emphasis on their relation to Maker-Breaker games and on the general importance of randomness in the study of such games. Amongst others, this will include connections to random graph properties on one the hand and the investigation of randomized strategies on the other hand.