ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let \cfG\cf G be a class of graphs, let CMSO1\xspace{\mathrm{CMSO}_1}\xspace denote counting monadic second-order logic with one free set-variable type, let τ\tau be a CMSO1\xspace{\mathrm{CMSO}_1}\xspace transduction, and let PtP_t denote the path on tt vertices. Transduction characterization conjecture. The class \cfG\cf G has bounded shrub-depth if and only if, for every CMSO1\xspace{\mathrm{CMSO}_1}\xspace transduction τ\tau, there exists an integer tt such that

Pt∉τ(\cfG).P_t\notin\tau(\cf G).

This conjecture proposes an asymptotic characterization of bounded shrub-depth through the transduction hierarchy: precisely the graph classes from which no counting monadic second-order transduction can produce paths of every length. The surrounding discussion presents it as plausible and does not give a resolution.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.