דילוג לניווט ראשי דילוג לחיפוש דילוג לתוכן הראשי

Bart-Moe games, JumbleG and discrepancy

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

5 ציטוטים ‏(Scopus)

תקציר

Let A and B be hypergraphs with a common vertex set V. In a (p, q, A ∪ B) Bart-Moe game, the players take turns selecting previously unclaimed vertices of V. 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 p vertices per move and the second player, called Moe (to denote his role as Maker or Enforcer), selects q vertices per move. Bart wins the game iff he has at least one vertex in every hyperedge B ∈ B and no complete hyperedge A ∈ A. We prove a sufficient condition for Bart to win the (p, 1) game, for every positive integer p. 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 frac(p, p + 1), and to a discrepancy game.

שפה מקוריתאנגלית
עמודים (מ-עד)1131-1143
מספר עמודים13
כתב עתEuropean Journal of Combinatorics
כרך28
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מאי 2007
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Bart-Moe games, JumbleG and discrepancy'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי