Shattering-extremal set systems of VC dimension at most 2

2014/07/11 by Mészáros, Tamás, Rónyai, Lajos
#05C20 #05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1407.3230

Abstract

We say that a set system F⊆ 2^[n] shatters a given set S⊆ [n] if 2^S=\F ∩ S : F ∈ F\. The Sauer inequality states that in general, a set system F shatters at least |F| sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly |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 from \citeVC1 about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension 2.

Related

• Shattering-extremal set systems of small VC-dimension
• Shattering-extremal set systems from Sperner families
• Standard monomials and extremal point sets
• Shattering-Extremal Systems
• Set Systems and Families of Permutations with Small Traces