Shattering-extremal set systems from Sperner families

We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an a...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2020-04, Vol.276, p.92-101
Main Authors: Kusch, Christopher, Mészáros, Tamás
Format: Article
Language:English
Subjects:
Gröbner bases
Sauer–Shelah lemma
Shattering
Sperner families
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer–Shelah lemma states that in general, a set system F shatters at least |F| sets. We concentrate on the case of equality and call a set system shattering-extremal if it shatters exactly |F| sets. Here we discuss an approach to study these systems using Sperner families and prove some preliminary results based on an earlier algebraic approach.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2019.07.016