Hefetz, Krivelevich and Tan's asymptotic Client-Waiter odd cycle game conjecture

Let OCn\mathcal{OC}_n denote the family of odd cycles on the board of the Client-Waiter game, and let bcw(OCn)b_{cw}(\mathcal{OC}_n) be its threshold bias. Hefetz, Krivelevich and Tan's conjecture.

bcw(OCn)=(1/2o(1))n.b_{cw}(\mathcal{OC}_n) = \big( 1/2 - o(1) \big) \,n.

The previously known bounds are (1/(4log2)o(1))nbcw(OCn)n/21\big(1/(4\log 2)-o(1)\big)n\leq b_{cw}(\mathcal{OC}_n)\leq\lceil n/2\rceil-1; the conjecture asserts that the upper bound is asymptotically tight.

Sources & referencesView supporting material

Primary source

Jan Corsten, Adva Mond, Alexey Pokrovskiy, Christoph Spiegel and Tibor Szabó, “On the Odd Cycle Game and Connected Rules”, arXiv:1906.04024 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.