Shattering-Extremal Set Systems of VC Dimension at most 2

  • Tamás Mészáros
  • Lajos Rónyai
Keywords: shattering, shattering-extremal set system, Vapnik-Chervonenkis dimension, inclusion graph


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$.

Author Biography

Tamás Mészáros, Central European University, Budapest
Department of Mathematics and its Applications
Article Number