Structural sparsity (Q2815673)

This is an extensive survey in a compact format of the notion of structural sparsity. This notion appears in various disguises in different areas, such as graph theory, information theory, model theory and algorithmic complexity. The survey systematically considers different topics in which structural sparsity appears in one or more of its disguises. Key theorems are listed in connection with each topic. Many of these theorems show that, in an appropriate context, structural sparsity can be characterized in more than one way, and the different characterizations can have quite different flavours. The topics and notions discussed include nowhere density, Vapnik-Chervonenkis dimension, stability, regular partitions, structural limits (and graphons), class speed, entropy, logarithmic densities, shallow (topological) minors, bounded expansion, tree depth, quasi-wideness, and algorithmic consequences of the mentioned concepts.