The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛

Krivelevich, Michael

doi:10.1090/S0894-0347-2010-00678-9

The critical bias for the Hamiltonicity game is $(1+o(1))n/\ln n$
HTML articles powered by AMS MathViewer

by Michael Krivelevich

J. Amer. Math. Soc. 24 (2011), 125-131

DOI: https://doi.org/10.1090/S0894-0347-2010-00678-9

Published electronically: August 31, 2010

PDF | Request permission

Abstract:

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)\le \left (1-\frac {30}{\ln ^{1/4}n}\right )\frac {n}{\ln n}$, for all large enough $n$.

References

József Beck, Random graphs and positional games on the complete graph, Random graphs ’83 (Poznań, 1983) North-Holland Math. Stud., vol. 118, North-Holland, Amsterdam, 1985, pp. 7–13. MR 860583
József Beck, Combinatorial games, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge University Press, Cambridge, 2008. Tic-tac-toe theory. MR 2402857, DOI 10.1017/CBO9780511735202
Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
B. Bollobás and A. Papaioannou, A biased Hamiltonian game, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), 1982, pp. 105–115. MR 725872
V. Chvátal and P. Erdős, Biased positional games, Ann. Discrete Math. 2 (1978), 221–229. MR 500701, DOI 10.1016/S0167-5060(08)70335-2
Heidi Gebauer and Tibor Szabó, Asymptotic random graph intuition for the biased connectivity game, Random Structures Algorithms 35 (2009), no. 4, 431–443. MR 2571778, DOI 10.1002/rsa.20279
Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó, Fast winning strategies in Maker-Breaker games, J. Combin. Theory Ser. B 99 (2009), no. 1, 39–47. MR 2467817, DOI 10.1016/j.jctb.2008.04.001
Dan Hefetz and Sebastian Stich, On two problems regarding the Hamiltonian cycle game, Electron. J. Combin. 16 (2009), no. 1, Research Paper 28, 18. MR 2482096, DOI 10.37236/117
Michael Krivelevich and Tibor Szabó, Biased positional games and small hypergraphs with large covers, Electron. J. Combin. 15 (2008), no. 1, Research Paper 70, 13. MR 2411447, DOI 10.37236/794
M. Krivelevich, E. Lubetzky and B. Sudakov, Hamiltonicity thresholds in Achlioptas processes, Random Structures and Algorithms 37 (2010), 1–24.
L. Pósa, Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), no. 4, 359–364. MR 389666, DOI 10.1016/0012-365X(76)90068-6