Stability conjecture for expressions constructed from transductions
Stability conjecture for expressions constructed from transductions
Let denote the class of reflexive -ary paths, let , and consider the -expressions constructed in the proof of the transduction lemma. A function should exist such that every such expression is -stable.
Expression-stability conjecture. There is a function such that each -expression constructed in the proof of the transduction lemma is -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.