Towards an arboretum of monadically stable classes of graphs
share
Logical transductions provide a very useful tool to encode classes of structures inside other classes of structures. In this paper we study first-order transductions and the quasi-order they induce on infinite hereditary classes of finite graphs. Surprisingly, this quasi-order is very complex, though shaped by the locality properties of first-order logic. This contrasts with the conjectured simplicity of the MSO transduction quasi-order. Main dividing lines inherited from classical model theory are the notions of monadic stability and monadic dependence. It appears that the FO transduction quasi-order has a great expressive power and many class properties studied earlier (such as having bounded pathwidth, bounded shrubdepth, etc.) may be equivalently defined by it. In this paper we study properties of the FO transduction quasi-order in detail, particularly in the monadically stable domain. Among other things we prove that the classes with given pathwidth form a strict hierarchy in the FO transduction quasi-order. Our basic results are based on a new normal form of transductions. We formulate several old and new conjectures. For example it is a challenging problem whether the classes with given treewidth form a strict hierarchy. This is illustrating the rich spectrum of an emerging area.
READ FULL TEXT