February 4, 2008
Thresholds for positional games
Tibor Szabò
ETH Zürich
The notion of positional games played an instrumental role in the development of the concept of derandomization in the theory of algorithms. In the talk we discuss two-player positional games played on the edge set of the complete graph. We investigate a mysterious phenomenon, the "random graph intuition", surrounding these games and settle a couple of long-standing open problems of the area.