Shattering-extremal set systems from Sperner families

2017/10/09 by Kusch, Christopher, Mészáros, Tamás
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1710.03165

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-Shelah lemma 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. A conjecture of Rónyai and the second author and of Litman and Moran states that if a family is shattering-extremal then one can add a set to it and the resulting family is still shattering-extremal. Here we prove this conjecture for a class of set systems defined from Sperner families.

Related

• Shattering-extremal set systems of VC dimension at most 2
• Shattering-extremal set systems of small VC-dimension
• Standard monomials and extremal point sets
• Shattering-Extremal Systems
• Shattering k-sets with Permutations