Stability conjecture for expressions constructed from transductions

About 1 year old · traced to

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:N→Ng:\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:N→Ng:\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.

References

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.