Shattering news (Q1348666)

A family \({\mathcal F}\) of subsets of \([m]=\{1,2,\dots,m\}\) is said to shatter a subset \(S\subseteq[m]\) if \(\{E\cap S:E\in{\mathcal F}\}=2^S\); \({\roman{ sh}}({\mathcal F})\) is defined to be \(\{S\subseteq[m]:{\mathcal F}\text{ shatters }S\}\). It is known [cf. \textit{A. Pajor}, Sous-espaces \(l^n_1\) des espaces de Banach. (Travaux en Cours. 16. Hermann, Paris) (1985)] that \(|\text{sh}({\mathcal F})|\geq|{\mathcal F}|\) (Theorem 1.1). The empty set \(\emptyset\) is order-shattered by \({\mathcal F}\) if \(|{\mathcal F}|=1\). If \(k>0\), \(1\leq s_1<s_2<\dots<s_k\leq m\), and \(T =\{s_k+1,s_k+2,\dots,m\}\), (possibly \(T=\emptyset\)), the set \(\{s_1,s_2,\dots,s_k\}\) is order-shattered by \({\mathcal F}\) if \({\mathcal F}\) admits a partition \({\mathcal F}=\widetilde{\mathcal F}_0\cup\widetilde{\mathcal F}_1\), where \(T\cap C=T\cap D\), \(s_k\notin C\), \(s_k\in D\), for all \(C\in\widetilde{\mathcal F}_0\) and \(D\in \widetilde{\mathcal F}_1\), and if both \(\widetilde{\mathcal F}_0\) and \(\widetilde{\mathcal F}_1\) individually order-shatter \(S-\{s_k\}\); \(\text{osh}({\mathcal F})\) is defined to be \(\{S\subseteq[m]:{\mathcal F}\) order-shatters \(S\}\). Theorem 1.4: \(|\text{osh}({\mathcal F})|=|{\mathcal F}|\). From the authors' abstract: This provides proofs and strengthenings of a result of \textit{N. Sauer} [On the density of families of sets. J. Comb. Theory, Ser. A 13, 145-147 (1972; Zbl 0248.05005)], \textit{S. Shelah} [A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41, 247-261 (1972; Zbl 0239.02024)], \textit{V. N. Vapnik} and \textit{A. Ya. Chervonenkis} [On the uniform convergence of relative frequencies of events to their probabilities. Theor. Probab. Appl. 16, 264-280 (1971); translation from Teor. Veroyatn. Primen. 16, 264-279 (1971; Zbl 0247.60005)] (sometimes known as Sauer's lemma) and a new approach to the reverse Sauer inequality of \textit{B. Bollobás} and \textit{A. J. Radcliffe} [Defect Sauer results. J. Comb. Theory, Ser. A 72, No. 2, 189-208 (1995; Zbl 0835.05082)]. We characterize those sets which can be order-shattered by a uniform family, and those sets which can be order-shattered by an antichain. We also give an algebraic interpretation of order shattering using Gröbner bases. This results in sharpening of a theorem of \textit{P. Frankl} and \textit{J. Pach} [On disjointly representable sets. Combinatorica 4, 39-45 (1984; Zbl 0534.05003)]. It also points out an interesting and promising connection between combinatorial and algebraic objects.