Cohomological VC-density: Bounds and Applications

Abstract

The concept of Vapnik-Chervonenkis (VC) density is pivotal across various mathematical fields, including discrete geometry, probability theory and model theory. In this paper, we introduce a topological generalization of VC-density. Let $Y$ be a topological space and $\mathcal{X}$ a family of closed subspaces of $Y$. For each $p\ge 0$, we define a number, ${\mathrm{vcd}}_{\mathcal{X}}^p$, which we refer to as the degree $p$ VC-density of the family $\mathcal{X}$. The classical notion of VC-density within this topological framework can be recovered by setting $p=0$. Our definition of degree $p$ VC-density extends to higher orders as well. For $p\ge 0$, $q\ge 1$, we define the degree $p$, order $q$ VC density ${\mathrm{vcd}}_{\mathcal{X}}^{p,q}$ of $\mathcal{X}$, which recovers Shelah's notion of higher order VC-density for $q$-dependent families when $p=0$. Our definition introduces a completely new notion when $p>0$. We examine the properties of ${\mathrm{vcd}}_{\mathcal{X}}^p$ (as well as ${\mathrm{vcd}}_{\mathcal{X}}^{p,q}$) when the families $\mathcal{X}$ are definable in structures with some underlying topology (for instance, the Euclidean topology for o-minimal structures over $\mathbb{R}$, the analytic topology over $\mathbb{C}$, or the étale site for schemes over arbitrary algebraically closed fields). Our main result establishes that in any model of these theories \[ \mathrm{vcd}_{\mathcal{X}}^p \leq (p+1) \dim X, \] and more generally for any $q\ge 1$ \[ \mathrm{vcd}^{p,q}_{\mathcal{X}} \leq (p+q) \dim X. \] We give examples to show that our bounds are optimal. We also present combinatorial applications of our higher-degree VC-density bounds, deriving higher degree topological analogs of well-known results such as the existence of $\epsilon$-nets and the fractional Helly theorem.

arXiv comment54 pages. Reorganized