Convex Geometries are Extremal for the Generalized Sauer-Shelah Bound
Keywords:
Sauer-Shelah lemma, Convex geometries, Extremal lattices
Abstract
The Sauer-Shelah lemma provides an exact upper bound on the size of set families with bounded Vapnik-Chervonekis dimension. When applied to lattices represented as closure systems, this lemma outlines a class of extremal lattices obtaining this bound. Here we show that the Sauer-Shelah bound can be easily generalized to arbitrary antichains, and extremal objects for this generalized bound are exactly convex geometries. We also show that the problem of classification of antichains admitting such extremal objects is NP-complete.