pith. machine review for the scientific record. sign in

arxiv: 1407.3230 · v2 · submitted 2014-07-11 · 🧮 math.CO

Recognition: unknown

Shattering-extremal set systems of VC dimension at most 2

Authors on Pith no claims yet
classification 🧮 math.CO
keywords mathcalshattering-extremaldimensionshatterssystemsystemscasesets
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. In this paper we characterize shattering-extremal set systems of Vapnik-Chervonenkis dimension $2$ in terms of their inclusion graphs, and as a corollary we answer an open question from \cite{VC1} about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension $2$.

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.