pith. sign in

arxiv: 1710.03165 · v1 · pith:2742VBPKnew · submitted 2017-10-09 · 🧮 math.CO

Shattering-extremal set systems from Sperner families

classification 🧮 math.CO
keywords mathcalshattering-extremalshatterssystemconjecturefamiliesfamilyhere
0
0 comments X
read the original abstract

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-Shelah lemma 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 \emph{shattering-extremal} if it shatters exactly $|\mathcal{F}|$ sets. A conjecture of R\'onyai 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.