We study the (hereditary) discrepancy of definable set systems, which is a natural measure for their inherent complexity and approximability. We establish a strong connection between the hereditary discrepancy and quantifier elimination over signatures with only unary relation and function symbols. We prove that set systems definable in theories (over such signatures) with quantifier elimination have constant hereditary discrepancy. We derive that set systems definable in bounded expansion classes, which are very general classes of uniformly sparse graphs, have bounded hereditary discrepancy. We also derive that nowhere dense classes, which are more general than bounded expansion classes, in general do not admit quantifier elimination over a signature extended by an arbitrary number of unary function symbols. We show that the set systems on a ground set $U$ definable on a monotone nowhere dense class of graphs $\mathscr C$ have hereditary discrepancy at most $|U|^{c}$ (for some~$c<1/2$) and that, on the contrary, for every monotone somewhere dense class $\mathscr C$ and for every positive integer $d$ there is a set system of $d$-tuples definable in $\mathscr C$ with discrepancy $\Omega(|U|^{1/2})$. We further prove that if $\mathscr C$ is a class of graphs with bounded expansion and $\phi(\bar x;\bar y)$ is a first-order formula, then we can compute in polynomial time, for an input graph $G\in\mathscr C$, a mapping $\chi:V(G)^{|\bar x|}\rightarrow\{-1,1\}$ witnessing the boundedness of the discrepancy of the set-system defined by~$\phi$, an $\varepsilon$-net of size $\mathcal{O}(1/\varepsilon)$, and an $\varepsilon$-approximation of size $\mathcal{O}(1/\varepsilon)$.
翻译:我们研究可定义集成系统的( 遗传性) 差异, 这是一种自然测量其内在复杂性和相近性的方法。 我们建立遗传差异和对签名的量化取消之间的紧密联系, 仅具有非性质关系和函数符号。 我们证明, 在理论( 此类签名) 中设定了可定义的系统, 且具有恒定性差异。 我们推论, 在约束的扩展类中设定了可定义的系统, 这些系统属于统一稀释图的非常普通的类别, 具有连带性差异。 我们还推论, 密级类( 普通值$ 美元), 通常不承认对由任意数的单函数符号扩展的签名进行量化消除。 我们证明, 设定的系统在单数级或密度的图形类别上可以确定美元( 美元) 基值( 普通值 美元), 而对于每单级( 美元) 的美元( 美元) 硬值( 硬值) 和 美元( 美元) 硬值( 美元) 的硬值( 硬值) 硬值) 的硬值( 硬值) 硬值) 硬值( C=( 美元) 硬值) 硬值) 硬值的系统确定。