Springer, Jun 13, 2014 - Mathematics - 146 pages
This text is based on a lecture course given by the authors in the framework of Oberwolfach Seminars at the Mathematisches Forschungsinstitut Oberwolfach in May, 2013. It is intended to serve as a thorough introduction to the rapidly developing field of positional games. This area constitutes an important branch of combinatorics, whose aim it is to systematically develop an extensive mathematical basis for a variety of two player perfect information games. These ranges from such popular games as Tic-Tac-Toe and Hex to purely abstract games played on graphs and hypergraphs. The subject of positional games is strongly related to several other branches of combinatorics such as Ramsey theory, extremal graph and set theory, and the probabilistic method. These notes cover a variety of topics in positional games, including both classical results and recent important developments. They are presented in an accessible way and are accompanied by exercises of varying difficulty, helping the reader to better understand the theory. The text will benefit both researchers and graduate students in combinatorics and adjacent fields.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Chapter 2 MakerBreaker Games
Chapter 3 Biased Games
Chapter 4 AvoiderEnforcer Games
Chapter 5 The Connectivity Game
Chapter 6 The Hamiltonicity Game
Other editions - View all
1)st move 2-coloring arbitrary assume Avoider Avoider’s binary tree BoxBreaker Breaker Breaker’s win Chapter coloring complete graph connectivity game contains d)-tree denote disjoint spanning trees draw edge set Enforcer exists FP’s free edge ftree(k game F game played game X,F graph G H-game Hamilton cycle Hamiltonicity game Hence hyperedge ith move k-uniform hypergraph leaf-vector least Lemma let F Lovász Local Lemma lower bound Maker claims Maker-Breaker game Maker’s graph Maker’s strategy Maker’s win minimum degree monochromatic monotone Neighborhood Conjecture non-planarity number of edges occupy pairing strategy perfect binary tree perfect matching game piecewise split positional games positive integer probabilistic intuition probability proof of Theorem prove random graph randomized algorithm second player spanning trees strategy for Maker Strategy Stealing strong game subgraph subset Theorem threshold bias Tic-Tac-Toe triangle game upper bound variable vertices weak game winning lines winning sets winning strategy wins the game