Martin Kutz
-
Weak Positional Games on Hypergraphs of Rank Three
dmtcs:3422 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3422
Weak Positional Games on Hypergraphs of Rank ThreeArticle
Authors: Martin Kutz 1
NULL
Martin Kutz
1 Max-Planck-Institut für Informatik
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.
Jos W.H.M. Uiterwijk, 2018, Set Matching with applications: An enhancement of the Hales–Jewett pairing strategy, ICGA Journal, 40, 3, pp. 129-148, 10.3233/icg-180053.