Shattering-extremal set systems of VC dimension at most 2
type: Item
instance of: scholarly article
title: Shattering-extremal set systems of VC dimension at most 2
zbMATH Open document ID: 1302.05201
author: Tamás Mészáros
author: Lajos Rónyai
published in: The Electronic Journal of Combinatorics
publication date: 2014-11-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1407.3230
full work available at URL: v21i4p30
review text: 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.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 6369276
zbMATH Keywords: shattering
zbMATH Keywords: shattering-extremal set system
zbMATH Keywords: Vapnik-Chervonenkis dimension
zbMATH Keywords: inclusion graph
MaRDI profile type: Publication
arXiv ID: 1407.3230
cites work: Shattering news
cites work: Reverse Kleitman Inequalities
cites work: Defect Sauer results
cites work: Q3222197
cites work: Embeddings and the trace of finite sets
cites work: Shattering, graph orientations, and connectivity
cites work: Some Combinatorial Applications of Gröbner Bases
cites work: Q4454950
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
description: scientific article; zbMATH DE number 6369276