Thesis of Nacim Oijid

Complexity of positional games on graphs

Start date: 01/09/2021
End date: 01/09/2024

Advisor: Eric Duchene
Coadvisor: Aline Parreau


The thesis investigates the theme of positional games, introduced by Erdos in the 1970s. In particular, three lines of research will be explored

- particular structures of hypergraphs for the game board
- the study of bridges between different winning conventions (maker-maker, maker-breaker, picker-chooser, avoider-enforcer)
- the study of parameterized complexity