Transductions between sparse graph classes

A transduction \(\tau\) is a mapping decoding graphs of a class \(\mathcal{C}\) from graphs of a class \(\mathcal{D}\) by nondeterministically coloring the input graph \(H\in \mathcal{D}\) and changing adjacency relation using a fixed logical formula to create a graph \(G\in \mathcal{C}\). Transductions appear to be the right notion of embedding in model-theoretic structure theory for finite graphs, and they are related to the conjectured limits of model-checking for both monadic second-order and first-order logic.

In this talk, we focus on the following question: Given a pair of sparse classes \(\mathcal{C}\) and \(\mathcal{D}\), is there a first-order transduction decoding \(\mathcal{C}\) from \(\mathcal{D}\)? We simplify such transductions using congested shallow minors, and we answer this question for a few important pairs of graph classes.