/Exposé en anglais/Talk in english/

The Maker-Breaker game is played on a hypergraph H. Maker and Breaker take turns coloring vertices of H, in red and blue respectively. Maker wins if she gets a monochromatic red edge at any point, otherwise Breaker wins. We present some state of the art around this game and then proceed with our own results. Our study is centered on the notion of danger at x, which is a subhypergraph representing an urgent threat that Breaker must hit with his next pick if Maker picks x. Applying this concept in hypergraphs of rank 3 i.e. in which all edges are of size at most 3, we provide a structural characterization of the winner with perfect play, as well as optimal strategies for both players based on danger intersections. A crucial corollary is that Maker has a winning strategy on H if and only if she can guarantee the appearance, within the first three rounds of play, of a very specific elementary subhypergraph on which she easily wins. As a consequence, we are able to determine the algorithmic complexity of deciding which player has a winning strategy on a given hypergraph: this problem, which is known to be PSPACE-complete on 6-uniform hypergraphs, is in polynomial time on hypergraphs of rank 3. Another consequence is that, if Maker has a winning strategy on a hypergraph H of rank 3, then she can get a monochromatic red edge in just O(log(|V(H)|)) rounds of play.

[Florian Galliot] (ATER au LaBRI )
https:///www-fourier.univ-grenoble-alpes.fr/~galliotf/index.php

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 ] .