/Exposé /Talk/

Positional games were introduced by Hales and Jewett in 1963. They are usually played on a hypergraph, and two players take turns claiming the vertices of the hypergraph until a hyperedge is filled up by one player. When this happens, the winning conditions depend on the convention played. The most studied convention, Maker-Breaker, is played on a hypergraph by two players: Maker and Breaker. Maker wins if she manages to claim all the vertices of a hyperedge, otherwise Breaker wins. This convention was proved PSPACE-complete by Schaefer in 1978, for hypergraphs of rank 11, and this result was improved in 2023 by Rahman and Watson for hypergraphs of rank 6.

In this talk, we will present three other positional game conventions, namely Avoider-Enforcer, Client-Waiter and Waiter-Client, together with the proof of the PSPACE-completeness of the first two, and the tractability of the last one for hypergraphs of small ranks.

[Nacim Oijid ] (LaBRI )
https://nacim-oijid.fr/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .