3D-grids are not transducible from planar graphs

Prelegent(ci)

Jakub Gajarský

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

2 kwietnia 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

3D-grids are not transducible from planar graphs

Seminarium

Seminarium „Teoria automatów”

---

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.

---