positional_games.md 2.71 KB
 Fabian Nuraddin Alexander Gabel committed Jul 02, 2021 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ``````# Research Area: Positional Games ### Working Groups: dm Positional games are a variety of combinatorial games between to players with perfect information. Let some hypergraph \$(X,\mathcal{F})\$ be given, where \$X\$ is a finite set and where \$\mathcal{F} \subseteq \mathcal{P}(X)\$ is a family of subsets. We call \$X\$ the *board* of the game and \$\mathcal{F}\$ the family of *winning sets*. Both players alternate in claiming unclaimed elements of the board, according to predefined rules, and the winner is determined through the winning sets. Some of the best known positional games are Tic-Tac-Toe and Hex. These are examples of so-called *strong games* (see e.g. [a]), where both players try to accomplish the same goal. Another variant are *Maker-Breaker games*, where Maker tries to accomplish some goal (e.g. claiming all edges of a spanning tree of some graph), while Breaker tries to prevent her from doing so. We also need to mention \$a,b\$*-biased* versions of these games, where Maker is allowed to claim (up to) \$a\$ and breaker is allowed to claim (up to) \$b\$ elements of the board. If \$a=b=1\$ we call the game *unbiased*. There are many natural games to consider, for example the *spanning tree game*, the *perfect matching game*, and the *Hamiltonicity game* (for an in-depth overview we refer the interested reader to [b]). Usually these games are played on the edge-set of a complete graph \$K_n\$ or a binomial random graph \$G_{n,p}\$. Typical questions amongst others to consider are for which \$b\$ a \$(1,b)\$-biased Maker-Breaker game turns from a Maker's win into a Breaker's win (see e.g. [c]) or how fast Maker can win a certain game (see e.g. [d]). ## "Literature" [a] J. Beck, **Combinatorial Games: Tic-Tac-Toe Theory**, Encyclopedia of Mathematics and Its Applications 114, Cambridge University Press, 2008 [c] V. Chvátal and P. Erdős, *Biased positional games*, Annals of Discrete Mathematics 2 (1978), 221–229 [d] [D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabó, *Fast winning strategies in Maker-Breaker games*, Journal of Combinatorial Theory Series B 99 (2009), 39–47.](https://doi.org/10.1016/j.jctb.2008.04.001) [b] D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabó, **Positional Games**, Birkhäuser Basel (2014) ## Research Topics Within this Resarch Area 1. [Fast Strategies in Waiter-Client games](fastwc.html) 2. [Waiter-Client games on random graphs](randomwc.html) `````` Yannick Mogge committed Jul 05, 2021 24 ``````3. [Maker-Breaker games with restrictions on random graphs](restricted_randommb.html) `````` Fabian Nuraddin Alexander Gabel committed Jul 02, 2021 25 26 27 28 `````` ## "Output": Publications and Manuscripts [CGHHMM2020] [D. Clemens, P. Gupta, F. Hamann, A. Haupt, M. Mikalački, and Y. Mogge. *Fast Strategies in Waiter-Client Games*, The Electronic Journal of Combinatorics 27(3) (2020), P3.57](https://doi.org/10.37236/9451)``````