The CMSO transduction characterization of bounded shrub-depth

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.

Sources & referencesView supporting material

Primary source

Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek and Patrice Ossona de Mendez, “Shrub-depth: Capturing Height of Dense Graphs”, arXiv:1707.00359 (2019).

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.