Julien Duron, University of Warsaw

Graphs of bounded degeneracy—graphs where the density E/V is bounded for all subgraphs—represent a very general and useful class of sparse graphs. However, they are not sufficiently “tame” to allow for an efficient Fixed-Parameter Tractable (FPT) first-order model checking algorithm. This is because they can hide arbitrarily complex structures at a bounded distance; for example, consider the 1-subdivision of a clique.

Classes of bounded expansion (BE) represent a subset of bounded degeneracy classes with the additional property of remaining degenerately bounded even after the contraction of bounded-radius sets. In particular, BE classes are “stable” under FO transduction, in the sense that any sparse class obtained via transduction from a BE class is itself a BE class.

BE classes play a key role in understanding sparse graph classes, enabling FO model checking algorithms in FPT time [DKT’10]. To lift our understanding of sparse classes to the dense regime, we are interested in finding a suitable dense analogue of bounded expansion classes. In this talk, we will show that translinear classes—those for which any transduction has linear neighborhood complexity—are, in a strong sense, the good candidates.