VC Dimensions and Regularity

The regularity lemma says that every discrete object can be partitioned into a small number of random-like subobjects. But how small is small? And can we make small smaller if we assume that our given object is simple? And what does it mean for a discrete object to be simple?

In this talk, I will answer some of these questions. Along the way, I will discuss many variants and generalizations of the classical notion of VC dimension, which turn out to be essential for answering the questions above.

Based on joint work with Lior Gishboliner and Asaf Shapira.