Abstract
The Critical Bias for the Hamiltonicity Game is n/ln n
Michael Krivelevich
Tel Aviv University
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.
No video available