Structural sparsity and beyond: an overview

The theory of sparse graph classes, developed by Nešetřil and Ossona de Mendez, is a field within graph theory whose aim is to study abstract notions of sparsity for graphs in search for generic combinatorial, algorithmic, and logical methods that exploit sparse character of the studied structure. It appears that the key two notions of this theory --- nowhere denseness and bounded expansion --- explain well the limitations of certain techniques and capture the boundary of tractability for many fundamental problems. For example, under certain complexity assumptions, a subgraph-closed class of graphs admits an efficient (precisely, fixed-parameter tractable) algorithm for model-checking first order logic if and only if this class is nowhere dense.

During the talk we will first give a quick introduction to the theory of sparse graphs, focusing on motivation and logical aspects, mostly connected to properties definable in first-order logic. Second, we will discuss connections between sparsity and stability, a notion from model theory introduced and studied by Shelah. It seems that these connections give rise to an intriguing transfer of techniques and results between the two fields. This part of the talk will be based on a joint work with Sebastian Siebertz and Szymon Toruńczyk.