1Central European University, Budapest 2Computer and Automation Research Institute, Hungarian Academy of Sciences and Institute of Mathematics, Budapest University of Technology and Economics
The electronic journal of combinatorics, Tome 21 (2014) no. 4
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$.
1
Central European University, Budapest
2
Computer and Automation Research Institute, Hungarian Academy of Sciences and Institute of Mathematics, Budapest University of Technology and Economics
@article{10_37236_4548,
author = {Tam\'as M\'esz\'aros and Lajos R\'onyai},
title = {Shattering-extremal set systems of {VC} dimension at most 2},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/4548},
zbl = {1302.05201},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4548/}
}
TY - JOUR
AU - Tamás Mészáros
AU - Lajos Rónyai
TI - Shattering-extremal set systems of VC dimension at most 2
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/4548/
DO - 10.37236/4548
ID - 10_37236_4548
ER -
%0 Journal Article
%A Tamás Mészáros
%A Lajos Rónyai
%T Shattering-extremal set systems of VC dimension at most 2
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4548/
%R 10.37236/4548
%F 10_37236_4548
Tamás Mészáros; Lajos Rónyai. Shattering-extremal set systems of VC dimension at most 2. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4548
