Shattering and more: Extending the complete object (Q2144328)

Summary: Let \(\mathcal{F}\subseteq 2^{[m]}\) be a family of subsets of \([m]=\{1, 2, \ldots, m\}\). For \(S\subseteq [m]\), let \(\mathcal{F}|_S\) be the trace \(\mathcal{F}|_S=\{B\cap S : B\in\mathcal{F}\}\), considered as a multiset. We say \(\mathcal{F}\) shatters a set \(S\subseteq [m]\) if \(\mathcal{F}|_S\) has all \(2^{|S|}\) possible sets (i.e. complete). We say \(\mathcal{F}\) has a shattered set of size \(k\) if \(\mathcal{F}\) shatters some \(S\subseteq [m]\) with \(|S|=k\). It is well known that if \(\mathcal{F}\) has no shattered \(k\)-set then \(|\mathcal{F}|\leqslant\binom{m}{k-1}+\binom{m}{k-2}+\cdots+\binom{m}{0}\). We obtain the same exact bound on \(|\mathcal{F}|\) (for \(m\) large enough) when forbidding less. Namely, given fixed positive integers \(t\) and \(k\), for every set \(S\subseteq [m]\) with \(|S|=k\), set families \(\mathcal{F}\) are such that \(\mathcal{F}|_S\) does not have both all possible sets \(2^S\) and specified additional sets occuring at least \(t\) times. Similar results are proven for double shattering, namely when \(\mathcal{F}|_S\) does not have all sets \(2^{|S|}\) appearing twice. The paper is written in matrix notation with trace replaced by configuration.