Geodesic
The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
Krivelevich, Michael 1
1 School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Journal of the American Mathematical Society, Tome 24 (2011) no. 1, pp. 125-131 Cet article a éte moissonné depuis la source American Mathematical Society

Voir la notice de l'article

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$.
DOI : 10.1090/S0894-0347-2010-00678-9

Krivelevich, Michael  1

1 School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel 
@article{10_1090_S0894_0347_2010_00678_9,
     author = {Krivelevich, Michael},
     title = {The critical bias for the {Hamiltonicity} game is (1+\ensuremath{\mathit{o}}(1))\ensuremath{\mathit{n}}/ln\ensuremath{\mathit{n}}},
     journal = {Journal of the American Mathematical Society},
     pages = {125--131},
     year = {2011},
     volume = {24},
     number = {1},
     doi = {10.1090/S0894-0347-2010-00678-9},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-2010-00678-9/}
}
TY  - JOUR
AU  - Krivelevich, Michael
TI  - The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
JO  - Journal of the American Mathematical Society
PY  - 2011
SP  - 125
EP  - 131
VL  - 24
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-2010-00678-9/
DO  - 10.1090/S0894-0347-2010-00678-9
ID  - 10_1090_S0894_0347_2010_00678_9
ER  - 
%0 Journal Article
%A Krivelevich, Michael
%T The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
%J Journal of the American Mathematical Society
%D 2011
%P 125-131
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-2010-00678-9/
%R 10.1090/S0894-0347-2010-00678-9
%F 10_1090_S0894_0347_2010_00678_9
Krivelevich, Michael. The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛. Journal of the American Mathematical Society, Tome 24 (2011) no. 1, pp. 125-131. doi: 10.1090/S0894-0347-2010-00678-9

[1] Beck, József Random graphs and positional games on the complete graph 1985 7 13

[2] Beck, József Combinatorial games 2008

[3] Bollobás, Béla Random graphs 2001

[4] Bollobás, B., Papaioannou, A. A biased Hamiltonian game Congr. Numer. 1982 105 115

[5] Chvátal, V., Erdős, P. Biased positional games Ann. Discrete Math. 1978 221 229

[6] Gebauer, Heidi, Szabó, Tibor Asymptotic random graph intuition for the biased connectivity game Random Structures Algorithms 2009 431 443

[7] Hefetz, Dan, Krivelevich, Michael, Stojaković, Miloš, Szabó, Tibor Fast winning strategies in Maker-Breaker games J. Combin. Theory Ser. B 2009 39 47

[8] Hefetz, Dan, Stich, Sebastian On two problems regarding the Hamiltonian cycle game Electron. J. Combin. 2009

[9] Krivelevich, Michael, Szabó, Tibor Biased positional games and small hypergraphs with large covers Electron. J. Combin. 2008

[10] Pósa, L. Hamiltonian circuits in random graphs Discrete Math. 1976 359 364

Cité par Sources :