Geodesic
Convex geometries are extremal for the generalized Sauer-Shelah bound
Bogdan Chornomaz1
1V.N. Karazin Kharkiv National University
The electronic journal of combinatorics, Tome 25 (2018) no. 2

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl
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.
DOI : 10.37236/7217
Classification : 05D05, 52A01, 68Q25
Mots-clés : Sauer-Shelah lemma, convex geometries, extremal lattices

Bogdan Chornomaz  1

1 V.N. Karazin Kharkiv National University 
Bogdan Chornomaz. Convex geometries are extremal for the generalized Sauer-Shelah bound. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7217
@article{10_37236_7217,
     author = {Bogdan Chornomaz},
     title = {Convex geometries are extremal for the generalized {Sauer-Shelah} bound},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/7217},
     zbl = {1388.05184},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7217/}
}
TY  - JOUR
AU  - Bogdan Chornomaz
TI  - Convex geometries are extremal for the generalized Sauer-Shelah bound
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7217/
DO  - 10.37236/7217
ID  - 10_37236_7217
ER  - 
%0 Journal Article
%A Bogdan Chornomaz
%T Convex geometries are extremal for the generalized Sauer-Shelah bound
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7217/
%R 10.37236/7217
%F 10_37236_7217

Cité par Sources :