jeudi 8 janvier 2026

par BUTEL Nathalie

Nacim Oijid, chercheur postdoctoral au département de mathématiques et de statistiques mathématiques de l’Université d’Umeå donnera un séminaire le 8 janvier 2026 à 14h, au Centre Inria d'Université Côte d'Azur dans la salle Euler Violet.

 

TITLE : 

On the complexity beyond Maker-Breaker positional games 

ABSTRACT : 

Positional games were introduced by Hales and Jewett in 1963. These games are typically played on a hypergraph, with two players taking turns claiming vertices until one player fills up a hyperedge. The winning conditions then depend on the convention being played. The most studied convention is Maker-Breaker, which is played by two players on a hypergraph: Maker and Breaker. Maker wins if she claims all the vertices of a hyperedge; otherwise, Breaker wins. Schaefer proved this convention to be PSPACE-complete in 1978 for hypergraphs of rank 11. This result was improved in 2023 by Rahman and Watson for hypergraphs of rank 6 and in 2025 by Galliot for hypergraphs of rank 4. 
In this talk, we will focus on two other perspectives on positional games. First, we will study the complexity of three well-known positional game conventions: Avoider-Enforcer, Client-Waiter, and Waiter-Client. Then, we will expand the scope of our study of positional games to consider scores in positional games.