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.
Welcome Olga Medrano Martín del Campo, a new member of the IBS Discrete Mathematics Group
The IBS discrete mathematics group welcomes Dr. Olga Medrano Martín del Campo, a new research fellow at the IBS Discrete Mathematics Group from August 1, 2026. She received her Ph.D. from the University of Chicago under the supervision of Prof. Maryanthe Malliaris. She is interested in Learning in Theoretical Computer Science and connections to Logic and Combinatorics.