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

About 7 years old · traced to

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/2−o(1)) n.b_{cw}(\mathcal{OC}_n) = \big( 1/2 - o(1) \big) \,n.

The previously known bounds are (1/(4log⁡2)−o(1))n≤bcw(OCn)≤⌈n/2⌉−1\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.

References

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.