Ndiamé Ndiaye

The Speed and Threshold of the Biased Hamilton Cycle Game

2021 · Procedia Computer Science

We show that there is a constant C such that for any b < n/ln n − Cn/(ln n)3/2, Maker can win the Maker-Breaker Hamilton cycle game in n + Cn/√ln n steps.