This submission formalizes the core of the sparsity theory of nowhere dense graph classes, following the lecture notes Sparsity of Michał Pilipczuk and Sebastian Siebertz. Its spine is the chain the notes build: nowhere dense classes are uniformly quasi-wide; the shallow minors of their members have subpolynomial edge density; an edge-density bound on shallow topological minors bounds admissibility; admissibility bounds the strong coloring number; the strong coloring number bounds the weak coloring number; and, composing the last four, nowhere dense classes have subpolynomial weak coloring numbers. Weak coloring numbers control how many distinct traces vertex neighborhoods leave on a set of vertices, and the submission ends with that consequence: nowhere dense classes have almost linear neighborhood complexity.

The concept surface has fifteen review units, eight definitions and seven theorems, one per notion and per result of that chain, with the notes' explicit bounds and all parameters as infima of explicit sets of naturals. The proof network is laid out on the archive rather than folded into single derivations: the weak-coloring-number theorem is a glue proof composing the four theorem concepts before it, the neighborhood-complexity theorem assumes that statement and adds the radius-1 trace counting, and the quasi-wideness proof assumes the two Ramsey statements of the submission Finite Ramsey Theorems for Pairs and Tuples.

Except for the neighborhood-complexity theorem, all material is from the lecture notes Sparsity of Michał Pilipczuk and Sebastian Siebertz, taught at the University of Warsaw; the numbering above follows the 2019/20 edition of the course, whose 2017/18 predecessor carries the same statements under sequential numbering. The neighborhood-complexity bound is due to Eickmeyer, Giannopoulou, Kreutzer, Kwon, Pilipczuk, Rabinovich and Siebertz; the radius-1 derivation from the weak coloring numbers formalized here follows Corollary 6b of Dreier, Mählmann, McCarty, Pilipczuk and Toruńczyk.