We study positional games (popular such games
include Tic-Tac-Toe, HEX, 5-in-a-row, Bridge-It) from a
probabilistic and algorithmic point of view.
The most important topics include: strategy stealing,
pairing strategy, Ramsey games, Maker/Breaker and Avoider/Forcer games,
probabilistic intuition, Erdos-Selfride Criterion, derandomization,
greedy potential function strategies, Lovasz Local Lemma, Neighborhood
Conjecture, biased games, critical bias, Beck's Criterion
The course is aimed at graduate students and higher level honours
undergraduates in mathematics and computer science.
There is no formal prerequisite, however, strong mathematical background
and familiarity with basic
concepts of graph theory and combinatorics is required (or expected
to be picked up within a short time).
Course grades will be based upon the final exam (taking place
at 12:15PM, February 16, one week after the last lecture)
Exercises: a quiz with one of the previous week's
homework exercises will be given each week. To obtain a "pass" on the
exercises, an overall 50% score will be expected.