The flip-width subpolynomial collapse conjecture

At least 2 years old · documented by

Let C\mathcal C be a hereditary graph class. For each r∈Nr\in\mathbb N, let fw⁡r(G)\operatorname{fw}_r(G) denote the flip-width of GG for robber speed rr.

Flip-width subpolynomial collapse conjecture. The following conditions are equivalent:

  1. C\mathcal C has almost bounded flip-width, that is, for every fixed r∈Nr\in\mathbb N and ε>0\varepsilon>0,
fw⁡r(G)=o(∣G∣ε)\operatorname{fw}_r(G)=o(|G|^\varepsilon)

for all G∈CG\in\mathcal C; 2. for every fixed r∈Nr\in\mathbb N,

fw⁡r(G)=o(∣G∣1/2)\operatorname{fw}_r(G)=o(|G|^{1/2})

for all G∈CG\in\mathcal C.

This predicts a collapse from the subpolynomial bound at exponent 1/21/2 to subpolynomial bounds at every positive exponent. The source presents it as a conjecture supported by the paper's evidence; its general validity remains open.

References

Primary source

Szymon Toruńczyk, “Flip-width: Cops and Robber on dense graphs”, arXiv:2302.00352 (2024).

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.