Shattering-extremal set systems of VC dimension at most 2 (Q470957): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / 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. | |||
Property / 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C20 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6369276 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
shattering | |||
Property / zbMATH Keywords: shattering / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
shattering-extremal set system | |||
Property / zbMATH Keywords: shattering-extremal set system / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Vapnik-Chervonenkis dimension | |||
Property / zbMATH Keywords: Vapnik-Chervonenkis dimension / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
inclusion graph | |||
Property / zbMATH Keywords: inclusion graph / rank | |||
Normal rank |
Revision as of 17:36, 30 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shattering-extremal set systems of VC dimension at most 2 |
scientific article |
Statements
Shattering-extremal set systems of VC dimension at most 2 (English)
0 references
13 November 2014
0 references
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.
0 references
shattering
0 references
shattering-extremal set system
0 references
Vapnik-Chervonenkis dimension
0 references
inclusion graph
0 references