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

By Michael Krivelevich. 2009

91 citations recorded by the source corpus.

We prove that in the biased (1 : b) Hamiltonicity Maker-Breaker game, played on the edges of the complete graph Kn, Maker has a winning strategy for b(n) ≤ ( 1− 30 ln n ) n lnn , for all large enough n.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/288a916c41a67f94f37d1b56e31bb38c581f256f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Benny Sudakov
2. Choongbum Lee
3. Deryk Osthus
4. D. Kühn
5. Dhruv Mubayi
6. John Lenz
7. David Conlon
8. Joonkyung Lee

In Discrete Mathematics and Combinatorics

1. Benny Sudakov
2. Choongbum Lee
3. Deryk Osthus
4. D. Kühn
5. Dhruv Mubayi
6. John Lenz
7. David Conlon
8. Sebastian M. Cioaba

In Geometry and Topology

1. Benny Sudakov
2. Michael Krivelevich
3. Choongbum Lee
4. Deryk Osthus
5. D. Kühn
6. David Conlon
7. Joonkyung Lee

Citations in the corpus

• Robust Hamiltonicity of Dirac graphs (2012, background): “Let A1 be the set of vertices of A0 which have at most n 4 neighbors in A0, and note that by the minimum degree condition of the graph G, every vertex in A1 has at least n 4 neighbors in B0.”