The critical bias for the Hamiltonicity game is (1+π(1))π/lnπ
Open Access
- 31 August 2010
- journal article
- Published byΒ American Mathematical Society (AMS)Β inΒ Journal of the American Mathematical Society
- Vol.Β 24 Β (1) , 125-131
Abstract
We prove that in the biased ( 1 : b ) (1:b) Hamiltonicity Maker-Breaker game, played on the edges of the complete graph K n K_n , Maker has a winning strategy for b ( n ) β€ ( 1 β 30 ln 1 / 4 β‘ n ) n ln β‘ n b(n)\le \left (1-\frac {30}{\ln ^{1/4}n}\right )\frac {n}{\ln n} , for all large enough n n .Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Hamiltonicity thresholds in Achlioptas processesRandom Structures & Algorithms, 2010
- Asymptotic random graph intuition for the biased connectivity gameRandom Structures & Algorithms, 2009
- On Two Problems Regarding the Hamiltonian Cycle GameThe Electronic Journal of Combinatorics, 2009
- Fast winning strategies in MakerβBreaker gamesJournal of Combinatorial Theory, Series B, 2009
- Combinatorial Games2008
- Biased Positional Games and Small Hypergraphs with Large CoversThe Electronic Journal of Combinatorics, 2008
- Random Graphs2001
- Random Graphs and Positional Games on the Complete Graph1985
- Biased Positional Games1978
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976