Submission date: 12 August 2021

Abstract:

We revisit a key idea from the interaction of model theory and combinatorics, the existence of large “indivisible” sets, called “ε-excellent“, in k-edge stable graphs (equivalently, Littlestone classes). Translating to the language of probability, we find a quite different existence proof for \epsilon-excellent sets in Littlestone classes, using regret bounds in online learning. This proof applies to any ε < 1/2, compared to < 1/2^{2^k} or so in the original proof. We include a second proof using closure properties and the VC theorem, with other advantages but weaker bounds. As a simple corollary, the Littlestone dimension remains finite under some natural modifications to the definition. A theme in these proofs is the interaction of two abstract notions of majority, arising from measure, and from rank or dimension; we prove that these densely often coincide and that this is characteristic of Littlestone (stable) classes. The last section lists several open problems.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2108.05569: pdf, ps.