Computer Science/Discrete Mathematics Seminar I

Avoider-Enforcer games are a misere version of somewhat more popular Maker-Breaker games. An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph H=(V,E) (typically the vertices of H are the edges of the complete graph Kn on n vertices, and the hyperedges of H correspond to subgraphs of Kn possessing some graph property). The players claim in turns previously unoccupied elements of V(H). Enforcer wins if by the end of the game he forces Avoider to claim a complete hyperedge e of H, Avoider wins otherwise. In a general version of the game the so called bias b is introduced to level up players' chances to win; Avoider claims one element of the board each time, while Enforcer answers by claiming b elements. Recently Hefetz, Krivelevich and Szabo observed that in general Avoider-Enforcer games are not bias-monotone -- there are some games where the outcome changes hands from Avoider's win to Enforcer's and back as the bias b increases. Therefore the notion of a critical bias, which is the minimal b for which Avoider wins, is ill-defined in general. This is in sharp contrast with Maker-Breaker games that are easily seen to be bias-monotone. In an attempt to resolve this somewhat disturbing and rather counterintuitive phenomenon we define a new version of Avoider-Enforcer games where a critical bias exists by the virtue of the definition of the rules of the game. In this talk I will discuss this new version and our results for it for several quite natural games. In particular, we were able to show that the critical bias in the new versions of the Avoider-Enforcer connectivity and Hamiltonicity games (the game is played on the edge set of the complete graph Kn; Enforcer wins iff by the end of the game Avoider's graph is connected and spanning/Hamiltonian, resp.) is asymptotically equal to n/ln n. A joint work with Dan Hefetz (Tel Aviv/ETH Zurich), Milos Stojakovic (Novi Sad) and Tibor Szabo (ETH Zurich).