Transduction order of graph classes embeddable in surfaces

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 AFOB\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.

Sources & referencesView supporting material

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.