Stability conjecture for expressions constructed from transductions

Let \caQr\ca Q_r^\circ denote the class of reflexive rr-ary paths, let N\ell\in\mathbb{N}, and consider the (\caQr,)(\ca Q_r^\circ,\ell)-expressions constructed in the proof of the transduction lemma. A function g:NNg:\mathbb{N}\to\mathbb{N} should exist such that every such expression is g()g(\ell)-stable.

Expression-stability conjecture. There is a function g:NNg:\mathbb{N}\to\mathbb{N} such that each (\caQr,)(\ca Q_r^\circ,\ell)-expression constructed in the proof of the transduction lemma is g()g(\ell)-stable.

The conjecture concerns the stability of the expressions arising when first-order transductions are applied to monadically stable graph classes admitting a product structure. A positive answer would combine with the cited structural theorems to characterize classes first-order transducible from classes admitting a product structure as perturbations of classes of bounded expression-stable reflexive-path clique-width.

Sources & referencesView supporting material

Primary source

Petr Hliněný and Jan Jedelský, “Transductions of Graph Classes Admitting Product Structure”, arXiv:2501.18326 (2025).

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.