First-order transducibility among classes of sparse graphs
- Speaker(s)
- Jeremi Gładkowski
- Language of the talk
- English
- Date
- June 6, 2025, 2:15 p.m.
- Room
- room 5060
- Seminar
- Seminar Algorithms
Transducibility is a notion from model theory that formalizes the idea of performing a logical operation on a graph. A class of graphs D is transducible from a class C if every graph from D can be obtained by applying such a fixed operation (transduction) to some graph from the class C. We prove several negative results about first-order transducibility for classes of sparse graphs:
- for every t ∈ N, the class of graphs of treewidth at most t + 1 is not transducible from the class of graphs of treewidth at most t;
- for every t ∈ N, the class of graphs with Hadwiger number at most t + 2 is not transducible from the class of graphs with Hadwiger number at most t; and
- the class of graphs of treewidth at most 4 is not transducible from the class of planar graphs.
These results are obtained by combining the known upper and lower bounds on the weak coloring numbers of the considered graph classes with the following two new observations:
- If a weakly sparse graph class D is transducible from a class C of bounded expansion, then for some k ∈ N, every graph G ∈ D is a k-congested depth-k minor of a graph H’ obtained from some H ∈ C by adding a universal vertex.
- The operations of adding a universal vertex and of taking k-congested depth-k minors, for a fixed k, preserve the degree of the distance-d weak coloring number of a graph class, understood as a polynomial in d.
This is joint work with Jakub Gajarský, Jan Jedelský, Michał Pilipczuk and Szymon Toruńczyk.