Olga Medrano Martín del Campo, Epsilon-saturation for Littlestone classes and stable graphs

We introduce the concept of the saturation of a (bi)graph: the union closure after inductively adding its virtual elements, which are weighted ε-good (respectively ε-excellent sets) as in the Stable Regularity Lemma. In the Littlestone class and stable graph case, we show that if the saturation has bounded Littlestone dimension, then it is the smallest ε-saturated object containing the initial one. We show that for certain values of ε, the saturations of Littlestone classes are Littlestone, although not necessarily of the same dimension. For ε large enough, we find examples to show that VC and Littlestone dimensions may grow arbitrarily. For certain ε, we bound Littlestone dimension of the saturation by a finite value depending on VC dimension, by using techniques including the Fundamental Theorem of Statistical Learning and the Littlestone Minimax Theorem. We will focus on the class (or bigraph) case and time permitting, we will discuss the stable graph case. Joint work with Maryanthe Malliaris and Shay Moran.