From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits

Abstract

This paper surveys the recent research related to the structural properties of sparse graphs and general finite relational structures. We provide a classification of classes of finite relational structures which is defined by means of a sequence of derived classes (defined by local changes). The resulting classification 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 finite 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 defined on the homomorphism order of graphs.