Optimal multivalued shattering (Q2910947)

Let \([n]\) and \((k)\) denote the sets \(\{1,2,\dots,n\}\) and \(\{0,1,\dots,k-1\}\), respectively. Let \(\mathcal{C} \subseteq (k)^n\) be a set of codewords (vectors). A codeword \(\mathbf{c}\) can be viewed as a function from \([n]\) to \((k)\). The code \(\mathcal{C}\) is said to shatter \(S \subseteq [n]\) if \(\{\mathbf{c} \mid_S : \mathbf{c} \in \mathcal{C}\} = (k)^S\), the set of all functions from \(S\) to \((k)\). We say that \(\mathcal{C}\) \((i,j)\)-shatters \(S \subseteq [n]\) if \(\mathcal{C} \mid_S\) contains all \(2^{|S|}\) functions from \(S\) to \(\{i,j\}\). Let \(k \geq 2\) be a fixed integer, and let \(\vec{s} = \{s_{0,1},s_{0,2},\dots,s_{k-2,k-1}\}\) be a positive integer vector of length \(\binom{k}{2}\) whose entries are indexed by ordered pairs \((i,j)\) with \(0 \leq i < j \leq k-1\). The main result of this paper is the following theorem. NEWLINENEWLINENEWLINE NEWLINESuppose that \(\mathcal{C} \subset (k)^n\) does not \((i,j)\)-shatter any coordinate set of size \(s_{i,j} \geq 1\) for every \(0 \leq i < j \leq k-1\). NEWLINEThen NEWLINE\[NEWLINE|\mathcal{C}| \leq NEWLINE\sum_{0 \leq a_{i,j} \leq s_{i,j}-1} NEWLINE\binom{n}{a_{0,1},a_{0,2},\dots,a_{k-2,k-1},n - NEWLINE\sum_{0 \leq i < j \leq k-1} a_{i,j}} = O(n^p),NEWLINE\]NEWLINE NEWLINEwhere the sum is taken for all possible choices of \(a_{i,j}\)'s and NEWLINE\(p = \sum_{0 \leq i < j \leq k-1} (s_{i,j}-1)\). On the other hand, when NEWLINE\(\vec{s}\) is fixed and \(n \to \infty\), there exists codes NEWLINE\(\mathcal{C} \subset (k)^n\) such that they do not \((i,j)\)-shatter any coordinate set of size \(s_{i,j} \geq 1\) for every \(0 \leq i < j \leq k-1\) and \(|\mathcal{C}| = \Omega(n^p)\).