Extremal hypergraphs for the biased Erdős-Selfridge theorem

Eric Lars Sundberg¹

¹Occidental College

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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

Détail

DOI : 10.37236/2394

Classification : 91A24, 91A43, 91A46
Mots-clés : positional game, Erdős-Selfridge theorem, hypergraph