pith. machine review for the scientific record. sign in

arxiv: 1211.0732 · v1 · submitted 2012-11-04 · 🧮 math.CO

Recognition: unknown

Shattering-extremal set systems of small VC-dimension

Authors on Pith no claims yet
classification 🧮 math.CO
keywords mathcalshatterssystemsystemsdimensionsetsshattering-extremalsubseteq
0
0 comments X
read the original abstract

We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a given set $S\subseteq [n]$ if $2^S={F \cap S : F \in \mathcal{F}}$. The Sauer inequality states that in general, a set system $\mathcal{F}$ shatters at least $|\mathcal{F}|$ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly $|\mathcal{F}|$ sets. We characterize shattering extremal set systems of Vapnik-Chervonenkis dimension 1 in terms of their inclusion graphs. Also from the perspective of extremality, we relate set systems of bounded Vapnik-Chervonenkis dimension to their projections.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.