Weak Positional Games on Hypergraphs of Small Rank, Perfect Play and Decomposition Theorems

alternately color the vertices of a hypergraph in their respective
colors; Maker trying to create a monochromatic edge of his color--
a Maker win--and Breaker trying to prevent this from happening.
If eventually all vertices of the hypergraph are colored and
Breaker has played in each edge then he wins.

First results about such games were obtained by Hales and Jewett
(1963) and Erd"os and Selfridge (1973). Since then, much work on
such coloring games focussed on criteria for Maker or Breaker
wins in terms of global parameters like the edge/vertex ratio or
the minimal vertex degree (Beck, 1981 and 1991) or at the
analysis of strategies for highly regular hypergraphs like multi-
dimensional grid cubes (Patashnik, 1980).

In this talk, we pursue a somewhat different approach to such
games, trying to give exact answers to the question whether a
given hypergraph constitutes a Maker or Breaker win situation.
Since this problem is known to be PSPACE-complete in general
(Schaefer, 1978), no satisfactory answer for arbitrary
hypergraphs should be expected. We focus on hypergraphs of
small rank. Our main result establishes a complete
characterization of winners and losers for almost-disjoint
hypergraphs (any two edges meet in at most one vertex) of rank 3
(no edge of size > 3) which gives a polynomial-time algorithm
for optimal play on such hypergraphs. This result is based on a
simple decomposition lemma for hypergraph games, which prompts
for more powerful generalizations that might lead to polynomial-
time algorithms for much larger classes of games.