Shattering-Extremal Set Systems of VC Dimension at most 2

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

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2014-11, Vol.21 (4)
Main Authors: Mészáros, Tamás, Rónyai, Lajos
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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$.
ISSN:1077-8926
1077-8926
DOI:10.37236/4548