Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets

2025/06/21 by Alon, Noga, Smorodinsky, Shakhar · 2 citations
#52C10 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.17777

Abstract

We define and study an extension of the notion of the VC-dimension of a hypergraph and apply it to establish a Tverberg type theorem for unions of convex sets. We also prove a new Radon type theorem for unions of convex sets, vastly improving the estimates in an earlier result of Bárány and Kalai.

Citations

• A Tverberg-type problem of Kalai: Two negative answers to questions of Alon and Smorodinsky, and the power of disjointness
• Helly type problems in convexity spaces
• Helly-type Problems
• Radon numbers grow linearly
• Radon partitions in convexity spaces

Cited by

• A Tverberg-type problem of Kalai: Two negative answers to questions of Alon and Smorodinsky, and the power of disjointness
• Strong invariants and Tverberg numbers in convexity spaces

Related

• Radon partitions in convexity spaces
• Helly type problems in convexity spaces
• Quantitative Tverberg, Helly, & Carathéodory theorems
• Optimal Bounds on the VC-dimension
• The VC-dimension of k-vertex d-polytopes