## Shattering news.(English)Zbl 0990.05123

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. 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 N. Sauer [On the density of families of sets. J. Comb. Theory, Ser. A 13, 145-147 (1972; Zbl 0248.05005)], 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)], V. N. Vapnik and 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 B. Bollobás and 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 P. Frankl and 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.

### MathOverflow Questions:

A Sauer-Shelah-like lermma for prefix tree

### MSC:

 05D05 Extremal set theory

order shattering
Full Text: