Weak Positional Games on Hypergraphs of Rank Three

Abstract

In a weak positional game, two players, Maker and Breaker, alternately claim vertices of a hypergraph until either Maker wins by getting a complete edge or all vertices are taken without this happening, a Breaker win. For the class of almost-disjoint hypergraphs of rank three (edges with up to three vertices only and edge-intersections on at most one vertex) we show how to find optimal strategies in polynomial time. Our result is based on a new type of decomposition theorem which might lead to a better understanding of weak positional games in general.

Keywords

• hypergraph
• positional game
• decomposition
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-hc] computer science [cs]/human-computer interaction [cs.hc]