The flip-width subpolynomial collapse conjecture

Let C\mathcal C be a hereditary graph class. For each rNr\in\mathbb N, let fwr(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 rNr\in\mathbb N and ε>0\varepsilon>0,
fwr(G)=o(Gε)\operatorname{fw}_r(G)=o(|G|^\varepsilon)

for all GCG\in\mathcal C; 2. for every fixed rNr\in\mathbb N,

fwr(G)=o(G1/2)\operatorname{fw}_r(G)=o(|G|^{1/2})

for all GCG\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.

Sources & referencesView supporting material

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.