Research Area: Positional Games

Working Groups: Lehrstuhl Diskrete Mathematik

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. [Be2008]), 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 [HKSS2014]). 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. [CE1978]) or how fast Maker can win a certain game (see e.g. [HKSS2009]).

Literature

[Be2008] J. Beck, Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and Its Applications 114, Cambridge University Press, 2008

[CE1978] V. Chvátal and P. Erdős, Biased positional games, Annals of Discrete Mathematics 2 (1978), 221–229

[HKSS2009] 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.

[HKSS2014] 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
2. Waiter-Client games on random graphs
3. Maker-Breaker games with restrictions
4. Games involving orientations

Publications and Manuscripts

[1] D. Clemens, A. Ferber, R. Glebov, D. Hefetz, and A. Liebenau. Building spanning trees quickly in Maker-Breaker games, SIAM Journal on Discrete Mathematics 29 (2015), 1683-1705.

[2] D. Clemens, A. Ferber, M. Krivelevich, and A. Liebenau. Fast strategies in Maker-Breaker games played on random boards, Combinatorics, Probability and Computing 21 (2012), 897-915.

[3] D. Clemens, H. Gebauer, and A. Liebenau. The random graph intuition for the tournament game, Combinatorics, Probability and Computing 25.1 (2016), 76-88.

[4] 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 (2020), no. 3, P3.57.

[5] D. Clemens, F. Hamann, Y. Mogge, and O. Parczyk, Maker-Breaker Games on Randomly Perturbed Graphs, SIAM Journal on Discrete Mathematics 35 (2021), no. 4, 2723–2748.

[6] D. Clemens, L. Kirsch, and Y. Mogge, Connector-Breaker Games on Random Boards, The Electronic Journal of Combinatorics 28 (2021), no. 3, P3.10.

[7] D. Clemens, and A. Liebenau. A non-trivial upper bound on the threshold bias of the Oriented-cycle game, Journal of Combinatorial Theory (2017), Series B 122, 21-54.

[8] D. Clemens, and M. Mikalački. A Remark on the Tournament Game, The Electronic Journal of Combinatorics 22 (2015), no. 3, P3-42.

[9] D. Clemens, and M. Mikalački. How fast can Maker win in fair biased games?, Discrete Mathematics 341 (2018), no. 1, 51–66.