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 ThreeConference paper

Authors: Martin Kutz 1

  • 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [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], [en] hypergraph, positional game, decomposition

3 Documents citing this article

Consultation statistics

This page has been seen 384 times.
This article's PDF has been downloaded 541 times.