Cohomological VC-density: Bounds and Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908390183141376 |
|---|---|
| author | Basu, Saugata Patel, Deepam |
| author_facet | Basu, Saugata Patel, Deepam |
| contents | 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 \geq 0$, we define a number, $\mathrm{vcd}^{p}_{\mathcal{X}}$, 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 \geq 0$, $q \geq 1$, we define the degree $p$, order $q$ VC density $\mathrm{vcd}^{p,q}_{\mathcal{X}}$ 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}^{p,q}_{\mathcal{X}}$) 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 \geq 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 $\varepsilon$-nets and the fractional Helly theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09670 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cohomological VC-density: Bounds and Applications Basu, Saugata Patel, Deepam Logic Algebraic Geometry Combinatorics Primary 03C52, 14F06, Secondary 14F20, 1425 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 \geq 0$, we define a number, $\mathrm{vcd}^{p}_{\mathcal{X}}$, 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 \geq 0$, $q \geq 1$, we define the degree $p$, order $q$ VC density $\mathrm{vcd}^{p,q}_{\mathcal{X}}$ 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}^{p,q}_{\mathcal{X}}$) 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 \geq 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 $\varepsilon$-nets and the fractional Helly theorem. |
| title | Cohomological VC-density: Bounds and Applications |
| topic | Logic Algebraic Geometry Combinatorics Primary 03C52, 14F06, Secondary 14F20, 1425 |
| url | https://arxiv.org/abs/2411.09670 |