Poset Positional Games

Guillaume Bagan (1, 2) , Eric Duchêne (2, 1) , Florian Galliot (3, 4) , Valentin Gledel (5, 6) , Mirjana Mikalački (7, 8) , Nacim Oijid (2, 1, 9) , Aline Parreau (1, 10) , Miloš Stojaković (8, 7)

1 GOAL - Graphes, AlgOrithmes et AppLications
2 LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
3 LaBRI - Laboratoire Bordelais de Recherche en Informatique
4 UB - Université de Bordeaux
5 LAMA - Laboratoire de Mathématiques
6 USMB [Université de Savoie] [Université de Chambéry] - Université Savoie Mont Blanc
7 Department of Mathematics and Informatics [Novi Sad]
8 University of Novi Sad
9 UCBL - Université Claude Bernard Lyon 1
10 LIRIS - Laboratoire International de Recherche sur les Images et la Scénographie

We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional structure -- a poset on the elements of the board. Throughout the game play, based on this poset and the set of the board elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is -- an element of the board can only be claimed if all the smaller elements in the poset are already claimed. We proceed to analyse these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. First we build a general framework around poset positional games. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

Keywords: Positional game; Poset; Connect 4; Maker-Breaker

Domains: Combinatorics [math.CO]

Guillaume Bagan, Eric Duchêne, Florian Galliot, Valentin Gledel, Mirjana Mikalački, et al.. Poset Positional Games. 2024. ⟨hal-04543617⟩