Hypergraphs and the Maker-Breaker game : a structural approach

Hypergraphes et jeu Maker-Breaker : une approche structurelle Cette thèse traite de jeux et d'hypergraphes. Nous nous concentrons tout particulièrement sur des jeux joués dans les hypergraphes, dont l'analyse s'avère conduire à l'étude de problèmes d'hypergraphes qui sont intéressants en soi. Les jeux positionnels mettent en scène deux joueurs qui sélectionnent tour à tour des sommets d'un hypergraphe, avec des objectifs variables: par exemple, au jeu du morpion, chaque joueur veut être le premier à posséder entièrement l'une des arêtes de l'hypergraphe. En convention Maker-Breaker, un joueur ("Maker") veut posséder entièrement l'une des arêtes, tandis que l'autre ("Breaker") veut l'en empêcher. Le thème principal est l'étude de structures dans les hypergraphes et leurs implications pour le jeu positionnel Maker-Breaker. En particulier, nous sommes intéressés par les hypergraphes de rang 3: cela signifie que toutes les arêtes sont de taille au plus 3, ce qui permet des résultats structurels et aide à comprendre le jeu Maker-Breaker dans ce cas. Un autre thème est la conception d'algorithmes en temps polynomial pour résoudre des jeux et des problèmes d'hypergraphes. Ces deux thèmes sont intimement liés, puisque toute caractérisation structurelle fournit un algorithme aussi efficace que la structure en question est simple.Le Chapitre I présente toutes les notions utilisées dans ce mémoire, ainsi que des résultats préliminaires. Après un état de l'art autour des jeux positionnels, nous introduisons notre approche structurelle du jeu Maker-Breaker, centrée sur une notion de dangers créés par Maker et que Breaker doit détruire immédiatement. Certaines structures élémentaires dans les hypergraphes, de rang 3 en particulier, sont aussi étudiées. Le Chapitre II réalise les études structurelles approfondies qui sont au coeur de ce mémoire. Nous obtenons une caractérisation structurelle de l'issue du jeu Maker-Breaker dans les hypergraphes de rang 3, ainsi que des stratégies optimales pour les deux joueurs, tout cela basé sur des propriétés d'intersections de dangers. Un lien direct apparaît avec un problème de connectivité dans les hypergraphes, pour lequel nous donnons une description structurelle fine des composantes connexes associées. Le Chapitre III récolte les fruits algorithmiques des études structurelles du chapitre précédent, et poursuit un peu plus loin. Nous expliquons comment les résultats structurels impliquent des algorithmes en temps polynomial, d'abord pour le calcul des composantes connexes susmentionnées, puis pour la résolution du jeu Maker-Breaker dans les hypergraphes de rang 3 comme corollaire. D'autres aspects de complexité du jeu, pas seulement algorithmique, sont également considérés. Le Chapitre IV concerne un problème de reconfiguration dans la grille carrée, d'un type qui peut être rapproché d'une version à un seul joueur du jeu Maker-Breaker. Nous rappelons quelques résultats de Demaine et. al., qui ont introduit ce problème. Un cas que les auteurs pensaient résolu s'avère compliqué, et nous apportons notre contribution à son étude.