The Critical Bias for the Hamiltonicity Game is n/ln n

Michael Krivelevich
Tel Aviv University
Mathematical Sciences

We prove that in the biased (1:b) Hamiltonicity Maker-Breaker game, played on the edges of the complete graph K_n, 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.

Back to Workshop I: Probabilistic Techniques and Applications