A Colorful Extension of VC-dimension and Geometric Applications
2026-07-11 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors introduce a new version of the VC-dimension that works with colored sets to better understand complex systems. Using this, they improve important geometric theorems related to convexity, including a sharper version of the Tverberg theorem with better scaling in parameters. They also prove new colorful versions of these theorems, which lead to improved selection and net theorems with better quantitative bounds than before. Finally, they extend their approach to more general shapes, broadening previous results. Overall, their work provides stronger and more general geometric results for abstract convex structures.
VC-dimensionTverberg theoremAbstract convexity spacesRadon numberColorful Tverberg theoremSelection lemmaε-net theorem(p,q)-theoremConvex sets
Authors
Chaya Keller, Shakhar Smorodinsky
Abstract
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 $D$ is not super-exponential. Second, we prove the first colorful $k$-wise Tverberg theorem for separable abstract convexity spaces. Using this theorem, we obtain a colorful selection lemma with $O(D^3)$ colors, an uncolored selection lemma for subsets of size $O(D^3)$, a weak $\varepsilon$-net theorem with nets of size $O_D(\varepsilon^{-O(D^3)})$, and a $(p,q)$-theorem with exponent of $\mathrm{poly}(D)$. All these quantitative bounds are significantly better than the best previously known general bounds for abstract convexity spaces. Finally, we extend our method to obtain a colorful Tverberg theorem for unions of convex sets, generalizing the uncolored theorem of Alon and Smorodinsky (SODA'26).