Research Topic: Orientation games
Collaborators (MAT): Dr. Dennis Clemens
Collaborators (external): Anita Liebenau, Heidi Gebauer, Mirjana Mikalački
In his breakthrough result, Beck [Be2008] proved that Maker, in an unbiased game on the complete graph \(K_n\), has a strategy to occupy a clique of size
\[ \lfloor 2\log_2 n − 2 \log_2 \log_2 n + 2 \log_2 e − 3 + o(1) \rfloor \]
with the bound being tight. The astonishing fact about this result is that a purely random game, i.e. both players pick their edges uniformly at random, is likely to lead to almost the same game outcome. Indeed, from the theory of random graphs (see e.g. [Bo2001]), it is known that in such a random game, Maker’s largest clique will be of size
\[ \lfloor 2\log_2 n − 2 \log_2 \log_2 n + 2 \log_2 e − 1 + o(1) \rfloor \]
with high probability. This strong connection between deterministic games and random graphs/strategies, usually referred to as probabilistic intuition, has been verified for a plethora of games since then.
Related to his result, Beck also considered the tournament game in which the winning sets are so-called tournaments (i.e. complete graphs with orientations on their edges) and in which Maker must give orientations to the edges that she claims. His aim was to find the largest integer \(k=k(n)\) such that Maker can occupy a copy of any pre-defined tournament \(\mathcal{T}_k\) on \(k\) vertices, and, due to an application of the probabilistic intuition, he conjectured this value to be \(k=(1-o(1))\log_2 n\). In [CGL2016] we however disproved the conjecture, and showed instead that \(k=(2-o(1))\log_2 n\), which in turn shows that the additional constraint of adding orientations does not make the game much harder for Maker.
Moreover, in [CM2015] we considered the same game, but played on a random graph \(G_{n,p}\) and with \(k\) being a constant. Surprisingly, it turned out that with high probability the outcome of the game does not depend much on the choice of the pre-defined tournament \(\mathcal{T}_k\) if \(k\geq 4\), while the two different tournaments on \(3\) vertices behave very different.
Finally, we [CL2017] also disproved a conjecture of Bollobás and Szabó [BS1998] on the threshold bias in the oriented cycle game. In this game, played on the complete graph \(K_n\), both players are required to give orientations to the edges that they claim. The first players wins if and only if the final tournament, which is created by both player together, contains an oriented cycle.
References
[Be2008] J. Beck. Combinatorial games: tic-tac-toe theory, Cambridge University Press, 2008.
[Bo2001] B. Bollobás. Random graphs, Cambridge University Press, 2001.
[BS1998] B. Bollobás, and T. Szabó. The oriented cycle game, Discrete Mathematics 186 (1-3), 55-67, 1998.
[CM2015] D. Clemens, and M. Mikalački. A Remark on the Tournament Game, The Electronic Journal of Combinatorics, P3-42, 2015.
