Article ID Journal Published Year Pages File Type
4650552 Discrete Mathematics 2008 7 Pages PDF
Abstract

A positional game is essentially a generalization of tic-tac-toe played on a hypergraph (V,F)(V,F). A pivotal result in the study of positional games is the Erdős–Selfridge theorem, which gives simple criteria for the existence of a Breaker's winning strategy on a hypergraph FF. It has been shown that the Erdős–Selfridge theorem can be tight and that numerous extremal systems exist for that theorem. We focus on a generalization of the Erdős–Selfridge theorem proven by Beck for biased (p:q)(p:q) games, which we call the (p:q)(p:q)–Erdős–Selfridge theorem. We show that for pn-uniform hypergraphs there is a unique   extremal system for the (p:q)(p:q)–Erdős–Selfridge theorem (q⩾2q⩾2) when Maker must win in exactly n turns (i.e., as quickly as possible).

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,