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

2009/09/15 by Michael Krivelevich, Krivelevich, Michael · 5 citations
Mathematics · #05C45 (Secondary) #05C57 (Primary) #91A43 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C45 #msc:05C57 #msc:91A43

paper · pdf · doi:10.48550/arxiv.0909.2744

9 pages

arxiv created 2010/03/09 · arxiv updated 2010/03/10

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)<=(1-o(1))n/ln n, for all large enough n.

Cited by

• The Maker-Breaker directed triangle game
• On the pancyclicity of 2-connected [5,3]-graphs
• Some Maker-Breaker games on hypergraphs
• Maker playing against an invisible Breaker
• Structure-biased Maker-Breaker Games

Related

• Asymptotically Optimal Threshold Bias for the (a : b) Maker-Breaker Minimum Degree, Connectivity and Hamiltonicity Games
• Biased Games On Random Boards
• Hamiltonian Maker-Breaker games on small graphs
• Maker Breaker on Digraphs
• Sharp thresholds for half-random games II