Breaker’s conjecture for doubly-biased component games

About 13 years old · traced to

Let GG be a dd-regular graph on nn vertices, where d≥3d\ge3, and let mm be a positive integer. In the (m:(d−2)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.

References

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.