Aryaman Jal: VC dimension, epsilon nets, and the art gallery problem

Abstract

The VC dimension of a set system is an important measure of its complexity and has found applications in computational and discrete geometry, statistics and more recently, additive combinatorics. We present a condensed introduction to the concept in a discrete geometry setting and exhibit its connection to generating small epsilon nets by random sampling. The proof of this is a classic application of the probabilistic method. If time permits, we'll also mention an application to the art gallery problem. The talk will be self-contained and no prior knowledge of discrete geometry will be required.