From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
Jaroslav NešetřilCharles University, Praha, Czech Republic
Patrice Ossona de MendezEcole des hautes études en sciences sociales, Paris, France
A subscription is required to access this book chapter.
This paper surveys the recent research related to the structural properties of sparse graphs and general ﬁnite relational structures. We provide a classiﬁcation of classes of ﬁnite relational structures which is deﬁned by means of a sequence of derived classes (deﬁned by local changes). The resulting classiﬁcation is surprisingly robust and it leads to many equivalent formulations which play an important role in applications in model theory, algorithmic graph theory and structural theory. One of these equivalent formulations guarantees a quick test for a ﬁnite type decomposition (called low tree depth decomposition). We give numerous examples from geometry and extremal graph theory and apply the result to dualities for special classes of graphs. Finally we characterize the existence of all restricted dualities in terms of limit objects induced by the convergence deﬁned on the homomorphism order of graphs.