VC dimension and a union theorem for set systems (Q2315444)

For a set \(X\), let \(2^{X} := \{A \colon A \subseteq X\}\), \(\binom{X}{\leq d} := \{A \subseteq X \colon |A| \leq d\}\), and \(\binom{|X|}{\leq d} := |\binom{X}{ \leq d}|\). For a positive integer \(n\), let \([n] := \{1, \dots, n\}\). For \(Y \subseteq [n]\) and \(\mathcal{A} \subseteq 2^{[n]}\), let \(\mathcal{A}_Y := \{A \cap Y \colon A \in \mathcal{A}\}\). The set \(Y\) is said to be shattered by \(\mathcal{A}\) if \(\mathcal{A}_Y = 2^Y\). Let \(\mathrm{sh}(\mathcal{A})\) denote the family of subsets of \(X\) that are shattered by \(\mathcal{A}\). The VC-dimension of \(\mathcal{A}\), denoted by \(\mbox{VC-dim}(\mathcal{A})\), is \(\max\{|Y| \colon Y \in\mathrm{sh}(\mathcal{A})\}\). The Sauer-Shelah lemma [\textit{N. Sauer}, J. Comb. Theory, Ser. A 13, 145--147 (1972; Zbl 0248.05005); \textit{S. Shelah}, Pac. J. Math. 41, 247--261 (1972; Zbl 0239.02024)] states that if \(\mbox{VC-dim}(\mathcal{A}) \leq d\), then \(|\mathcal{A}| \leq \binom{n}{ \leq d}\). For any binary set operation \(\star\) (such as \(\cup\), \(\cap\), and \(\triangle\)), let \(\star \mathcal{A}^k := \{A_1 \star \dots \star A_k \colon A_1, \dots, A_k \in \mathcal{A}\}\). Let \(p(n,k,d)\) be the size of a largest subfamily \(\mathcal{A}\) of \(2^{[n]}\) such that every member of \(\bigcup \mathcal{A}^k\) is of size at most \(d\). Let \(p'(n,k,d)\) be the size of a largest subfamily \(\mathcal{A}\) of \(2^{[n]}\) such that \(\mbox{VC-dim}(\triangle \mathcal{A}^k) \leq d\). \textit{P. Frankl} [Discrete Math. 26, 111--118 (1979; Zbl 0397.05004)] conjectured that for any positive integers \(n\), \(k\), and \(d \leq n\), \(p(n,k,d) = \max \{2^{d-ki}\binom{n - d + ki}{\leq i} \colon 0 \leq i \leq d/k\}\). \textit{P. Frankl} [Stud. Sci. Math. Hung. 11, 1--6 (1976; Zbl 0438.05001)] proved that if \(0 \leq r \leq k-1\) such that \(d \equiv r \pmod k\), then there exists an integer \(n_0\) such that \(p(n,k,d) = 2^{r}\binom{n-r}{\leq \lfloor d/k \rfloor}\) for every \(n \geq n_0\). The authors provide a new proof of this result. Using a compression method, the authors show that \(p'(n,k,d) = p(n,k,d)\) for any \(n\), \(k\), and \(d \leq n\). Together with Frankl's result, this generalizes an upper bound on \(p'(n,2,d)\) of \textit{Z. Dvir} and \textit{S. Moran} [Electron. J. Comb. 25, No. 4, Research Paper P4.38, 7 p. (2018; Zbl 1400.05250)], and settles one of their questions. The authors also show that for \(d \leq n\), there exists a subfamily \(\mathcal{A}\) of \(2^{[n]}\) such that \(\mbox{VC-dim}(\bigcup \mathcal{A}^2) \leq d\), \(\mbox{VC-dim}(\bigcap \mathcal{A}^2) \leq d\), and \(|\mathcal{A}| (n/d)^d\). This provides a negative answer to another question of \textit{Z. Dvir} and \textit{S. Moran} [Electron. J. Comb. 25, No. 4, Research Paper P4.38, 7 p. (2018; Zbl 1400.05250)].