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.
|
|
|
|