Tomasz Łuczak
Random graphs and positional games
Abstract:
It is well known that one can predict the result of some deterministic perfect information games between two players using the "random strategy heuristic", i.e. it is often the case that the player who has larger chances to win when both players are playing randomly is also the one who wins the game when both both players are playing their best strategies. This rather surprising phenomenon was first observed by Erdős and Selfridge and then studied and explored in a number of papers. In the talk we report on some recent results concerning so called Waiter-Client games on graphs, and follow the random strategy approach to analyze it.
This is a joint work with Małgorzata Bednarska-Bzdęga, Danny Hefetz, and Michael Krivelevich.