3D-grids are not transducible from planar graphs

Speaker(s)

Jakub Gajarský

Affiliation

University of Warsaw

Language of the talk

English

Date

April 2, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

3D-grids are not transducible from planar graphs

Seminar

Seminar Automata Theory

---

We prove that the class of 3D-grids cannot be obtained by a first-order transduction from the class of planar graphs, and more generally, from any class of graphs of bounded genus. This is a part of a more general research agenda, in which we try to understand when one graph class is not transducible from another graph class. Given how important transductions have proven to be recently (for example in the recent advances in the FO model checking problem), surprisingly little is known about this problem, with many natural questions being open.

Independently of our work, the same result about 3D-grids was simultaneously obtained by Jan Jedelský and Petr Hliněný. I will also briefly discuss the ideas behind their proof.

Joint work with Michał Pilipczuk and Filip Porkývka.

---