Breaker’s conjecture for doubly-biased component games

Let GG be a dd-regular graph on nn vertices, where d3d\ge3, and let mm be a positive integer. In the (m:(d2)m)(m:(d-2)m) game on GG, Breaker’s conjecture. Breaker can force Maker to build only connected components of size o(n)o(n), perhaps polylogarithmic or even logarithmic in nn. This asks whether Breaker can still prevent large Maker components at the critical bias, where the strategy discussed in the paper is inadequate; the conjectured bound is left open.

Sources & referencesView supporting material

Primary source

Rani Hod and Alon Naor, “Component Games on Regular Graphs”, arXiv:1301.0282 (2013).

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.