Extremal Hypergraphs for the Biased Erdős-Selfridge Theorem

  • Eric Lars Sundberg
Keywords: Positional games

Abstract

A positional game is essentially a generalization of Tic-Tac-Toe played on a hypergraph $(V,{\cal F}).$  A pivotal result in the study of positional games is the Erdős–Selfridge theorem, which gives a simple criterion for the existence of a Breaker's winning strategy on a finite hypergraph ${\cal F}$.  It has been shown that the bound in the Erdős–Selfridge theorem can be tight and that numerous extremal hypergraphs exist that demonstrate the tightness of the bound. We focus on a generalization of the Erdős–Selfridge theorem proven by Beck for biased $(p:q)$ games, which we call the $(p:q)$–Erdős–Selfridge theorem.  We show that for $pn$-uniform hypergraphs there is a unique extremal hypergraph for the $(p:q)$–Erdős–Selfridge theorem when $q\geq 2$.

Published
2013-02-05
Article Number
P26