Combinatorics Seminar
When: Sunday, June 17, 10am
Where: Schreiber 309
Speaker: Alon Naor, Tel Aviv University
Title: Avoider-Enforcer games played on edge disjoint
hypergraphs
Abstract:
A biased (p:q) Avoider-Enforcer positional game consists of a hypergraph
H=(X,F), and two players, Avoider and Enforcer, alternately claiming
previously unclaimed elements of X; Avoider claims p elements per move
and Enforcer claims q elements per move. At the end of the game (i.e.
when all the elements of X have been claimed), Avoider loses if he has
claimed all the elements of some hyperedge f from F, and wins otherwise.
These games are not bias monotone, that is, claiming less elements per
move is not necessarily an advantage. There is a bias monotone version
of the game in which each player claims at least p or q elements per
move, respectively.
A natural example of these games is the game Box, where the board
consists of n disjoint boxes, and Avoider tries to avoid claiming all
the elements in one of the boxes (The Maker-Breaker version of the game
was considered by Chvatal and Erdos in their seminal paper from 1978 and
has been frequently used ever since.) In this talk we present sufficient
conditions - including explicit strategies - for both Avoider's win and
Enforcer's win, under both versions of the game. These results are applied
then to investigate other Avoider-Enforcer games, played on various
boards, for example games played on the edge set of a random graph G(n,p).
Joint work with Asaf Ferber and Michael Krivelevich.