
Extended VC-dimension and Radon Type Theorems for Unions of Convex Sets
Noga Alon, speaking in the Institute for Advanced Study's Computer Science and Discrete Mathematics seminar, presents joint work with Shakhar Smorodinsky on an extension of VC-dimension, a concept from combinatorics and learning theory that measures the complexity of a hypergraph. Alon shows how this extended notion can be used to prove a Tverberg type theorem for unions of convex sets, a generalization of classical convexity results to collections built from multiple convex pieces rather than single points. He also presents a new Radon type theorem for unions of convex sets, resolving a question Gil Kalai posed in the 1970s. The talk moves through the definitions, the combinatorial machinery connecting VC-dimension to geometric partition theorems, and the proof ideas behind the new Radon result, aimed at an audience with background in discrete mathematics and combinatorial geometry.