A Colorful Extension of VC-dimension and Geometric Applications
The VC-dimension is a fundamental measure of the complexity of a set system. In this paper, we introduce and study a colorful variant of VC-dimension that captures the behavior of set systems on colored ground sets. By studying this new notion, we obtain a variety of geometric results. First, we prove that separable abstract convexity spaces with Radon number $D$ admit a Tverberg theorem with Tverberg number $O(D^2 r \log r)$. This bound significantly improves the $O(Dr^2\log r)$ bound of Alon and Smorodinsky from SODA'26 and is the first quasi-linear bound in $r$, in which the dependence on…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.10496
curl -X POST /api/v1/records/arxiv/2607.10496/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.10496/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'