کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646626 1342308 2016 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Economical extremal hypergraphs for the Erdős–Selfridge theorem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Economical extremal hypergraphs for the Erdős–Selfridge theorem
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 9, 6 September 2016, Pages 2329–2344
نویسندگان
, ,