Shattering-extremal set systems of VC dimension at most 2 (Q470957): Difference between revisions

Summary: 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 about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension 2.