کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646626 | 1342308 | 2016 | 16 صفحه PDF | دانلود رایگان |

A positional game is essentially a generalization of tic-tac-toe played on a hypergraph (V,H)(V,H). 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 HH. 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 call an extremal hypergraph economical if it is nn-uniform and Maker has an nn-turn winning strategy on that hypergraph. While characterizing all extremal hypergraphs for the Erdős–Selfridge theorem is still an open problem, we make progress on this problem by giving two distinct characterizations of the economical extremal hypergraphs for the Erdős–Selfridge theorem: one of a theoretical nature, and one of a more practical nature.
Journal: Discrete Mathematics - Volume 339, Issue 9, 6 September 2016, Pages 2329–2344