The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛

Michael Krivelevich

Source record

Source: Crossref

Published: Aug 31, 2010

DOI: 10.1090/s0894-0347-2010-00678-9

Open original source ↗

Source 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 .

Evidence graph

No public relationships recorded yet.

Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.

The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛 — Mathematical Frontier Network