Transduction order of graph classes embeddable in surfaces

About 1 year old · traced to

A surface is a compact 22-dimensional manifold without boundary. Write Σ≼Γ\Sigma\preccurlyeq\Gamma if every graph embeddable in Σ\Sigma is also embeddable in Γ\Gamma, and let EΣ\mathscr{E}_\Sigma be the class of graphs embeddable in Σ\Sigma. Write A⊑FOB\mathscr{A}\sqsubseteq_{\mathsf{FO}}\mathscr{B} when A\mathscr{A} is first-order transducible from B\mathscr{B}.

Surface transduction-order conjecture. Let Σ\Sigma and Γ\Gamma be surfaces such that Σ⋠Γ\Sigma\not\preccurlyeq\Gamma. Then

EΣ̸⊑FOEΓ.\mathscr{E}_\Sigma\not\sqsubseteq_{\mathsf{FO}}\mathscr{E}_\Gamma.

This conjecture asserts that, among graph classes embeddable in fixed surfaces, the obvious inclusions are the only transducibility relations. It is not known even for the torus and the sphere, where it asks whether toroidal graphs are first-order transducible from planar graphs.

References

Primary source

Michał Pilipczuk, “Graph classes through the lens of logic”, arXiv:2501.04166 (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.