## The critical bias for the Hamiltonicity game is $(1+o(1))n/\ln n$

HTML articles powered by AMS MathViewer

- by Michael Krivelevich PDF
- J. Amer. Math. Soc.
**24**(2011), 125-131 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** - 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** - 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

## Additional Information

**Michael Krivelevich**- Affiliation: School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel
- Email: krivelev@post.tau.ac.il
- Received by editor(s): October 26, 2009
- Received by editor(s) in revised form: March 9, 2010
- Published electronically: August 31, 2010
- Additional Notes: This research was supported in part by a USA-Israel BSF grant, by a grant from the Israel Science Foundation, and by a Pazy Memorial Award.
- © Copyright 2010
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc.
**24**(2011), 125-131 - MSC (2010): Primary 05-XX; Secondary 91-XX
- DOI: https://doi.org/10.1090/S0894-0347-2010-00678-9
- MathSciNet review: 2726601