Discrepancy and Sparsity

Abstract

We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs $H$ of a graph $G$ of the neighborhood set system of $H$ is sandwiched between $\Omega (\log \mathrm{deg}(G))$ and $\mathcal{O}(\mathrm{deg}(G))$, where $\mathrm{deg}(G)$ denotes the degeneracy of $G$. We extend this result to inequalities relating weak coloring numbers and discrepancy of graph powers and deduce a new characterization of bounded expansion classes. Then, we switch to a model theoretical point of view, introduce pointer structures, and study their relations to graph classes with bounded expansion. We deduce that a monotone class of graphs has bounded expansion if and only if all the set systems definable in this class have bounded hereditary discrepancy. Using known bounds on the VC-density of set systems definable in nowhere dense classes we also give a characterization of nowhere dense classes in terms of discrepancy. As consequences of our results, we obtain a corollary on the discrepancy of neighborhood set systems of edge colored graphs, a polynomial-time algorithm to compute $\epsilon$-approximations of size $\mathcal{O}(1/\epsilon )$ for set systems definable in bounded expansion classes, an application to clique coloring, and even the non-existence of a quantifier elimination scheme for nowhere dense classes.

Submitted version

Cited by in corpus (1)

• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes