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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references