Dissertação de Mestrado - Handel Scholze Marques

Combinatorial Games and the neighborhood conjecture

Combinatorial Games is the study of games with perfect information, this means that all players have knowledge of all possible moves, also there isn't luck or skill involved in performing a move, so, in theory, perfect play is possible. Examples of games like these are tic-tac-toe, chess, checkers, nim... the list goes on. In this dissertation we focus on the Maker-Breaker game, it has two players who each sequentially pick a vertex from a hypergraph, the goal of Maker is to claim all vertices of an edge, the goal of Breaker is to prevent this. We study in which types of hypergraph Maker or Breaker wins and what are the winning strategies. In particular, we consider how this question is related to the degrees of vertices in the hypergraph. We make use of Probability Theory, general Graph Theory, Satisfiability problems and more.