Discrepancy and Sparsity

arXiv2105.03693MaRDI QIDQ6367161FDOQ6367161

Authors: Yiting Jiang, P. Ossona de Mendez, Sebastian Siebertz, Alexandre Vigny 

Publication date: 8 May 2021

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(logmathrmdeg(G))$ and $mathcalO(mathrmdeg(G))$, where $mathrmdeg(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 $varepsilon$-approximations of size $mathcalO(1/varepsilon)$ 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.

This page was built for publication: Discrepancy and Sparsity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367161)