A uniform version of a theorem by Dvir and Moran (Q2166116)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A uniform version of a theorem by Dvir and Moran |
scientific article |
Statements
A uniform version of a theorem by Dvir and Moran (English)
0 references
23 August 2022
0 references
Let \(d \leq n\) be integers. Let \(\mathcal{F}\) be a uniform family of subsets of \([n] := \{1, 2, \ldots, n\}\), i.e., all members of \(\mathcal{F}\) have the same size. Let the VC-dimension of the family \(\mathcal{F} \Delta \mathcal{F} := \{ A \Delta B : A, B \in \mathcal{F}\}\) be at most \(d\). Then the main result shows that \(\vert \mathcal{F}\vert \leq 2 \binom{n}{\lfloor d/2 \rfloor}\). The author also proposes the following conjecture.\par Let \(0 \leq d < n\) be integers with \(d \equiv r \pmod{2}\) for some \(r \in \{0, 1\}\). Let \(\mathcal{F}\) be an uniform family of subsets of \([n]\) with VC-dimension at most \(d\). Then it is conjectured that \(\vert \mathcal{F}\vert \leq 2^r \binom{n-r}{\lfloor d\rfloor}\).
0 references
shattered set
0 references
Gröbner basis
0 references
extremal set theory
0 references
0 references