Convex Geometries are Extremal for the Generalized Sauer-Shelah Bound

  • Bogdan Chornomaz V.N. Karazin Kharkiv National University
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.

 

Published
2018-06-08
Article Number
P2.35