Combinatorics Seminar

When: Sunday, October 25, 10am Where: Schreiber 309 Speaker: Michael Krivelevich, Tel Aviv University Title: The critical bias for the Hamiltonicity game is n/ln n

Abstract:

Consider the following game between two players, called Maker and Breaker. The players change turns in claiming previously unoccupied edges of the complete graph K_n on n vertices, with Breaker moving first. Breaker takes b edges each time, Maker claims a single edge. Maker wins if and only if his graph contains a Hamilton cycle by the end of the game.

We prove that in this game Maker has a winning strategy for b(n)<(1-o(1))n/ln n, for all large enough n. This settles one of the longest standing problems in the theory of positional games.