کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654503 1632837 2007 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bart–Moe games, JumbleG and discrepancy
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bart–Moe games, JumbleG and discrepancy
چکیده انگلیسی

Let AA and BB be hypergraphs with a common vertex set VV. In a (p,q,A∪B)(p,q,A∪B) Bart–Moe game, the players take turns selecting previously unclaimed vertices of VV. The game ends when every vertex has been claimed by one of the players. The first player, called Bart (to denote his role as Breaker and Avoider together), selects pp vertices per move and the second player, called Moe (to denote his role as Maker or Enforcer), selects qq vertices per move. Bart wins the game iff he has at least one vertex in every hyperedge B∈BB∈B and no complete hyperedge A∈AA∈A. We prove a sufficient condition for Bart to win the (p,1)(p,1) game, for every positive integer pp. We then apply this criterion to two different games in which the first player’s aim is to build a pseudo-random graph of density pp+1, and to a discrepancy game.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 28, Issue 4, May 2007, Pages 1131–1143
نویسندگان
, , ,