The hereditary-discrepancy characterization of nowhere dense classes

Let $\mathscr{C}$ be a monotone class of finite graphs. For a partitioned formula $mathvarphi(\bar{x};\bar{y})$, let $\mathscr{S}^{mathvarphi}(G)$ denote the associated set system, and let $mathop{\mathrm{herdisc}}$ denote hereditary discrepancy. Then, for every $mathvarepsilon>0$ and every $G\inmathscr{C}$, the quantity $\left|\bigcup \mathscr{S}^{\varphi}(G)\right|$ is the size of the ground set used in the bound.

Hereditary-discrepancy characterization. A monotone class $\mathscr{C}$ is nowhere dense if and only if, for every partitioned formula $\varphi(\bar{x};\bar{y})$, every $\varepsilon>0$, and every $G\in\mathscr{C}$,

$$\mathrm{herdisc}(\mathscr{S}^{\varphi}(G))\in \mathcal{O}\left(\left|\bigcup \mathscr{S}^{\varphi}(G)\right|^{\varepsilon}\right).$$

This is presented as an equivalence and is proved in the paper through the implications developed around the displayed statement. It characterizes nowhere dense classes by subpolynomial hereditary-discrepancy bounds for all formula-defined set systems.