Sparsity: from graphs to relational structures

Nowhere density is a seminal notion in algorithmic graph theory and combinatorics, that generalises numerous well-behaved properties of classes of finite graphs. For monotone classes, nowhere density appears to be a key dividing line that separates tame from wild behaviour. From the perspective of model theory, Adler and Adler established that the monotone nowhere dense classes are precisely those that are monadically NIP, i. e. they do not transduce the class of all graphs, and conjectured that the same phenomenon occurs for classes of arbitrary relational structures and their corresponding Gaifman graphs. In this talk, I discuss recent results of Braunfeld, Dawar, Eleftheriadis, and Papadopoulos (2023) that settle the question of Adler-Adler, and survey few results from graph sparsity theory that generalise to the relational setting. Contributed talk given by Ioannis Eleftheriadis

Authors

• Ioannis Eleftheriadis

Keywords

No keywords are indexed for this paper.