Shattering-extremal set systems of small VC-dimension (Q1952706)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Shattering-extremal set systems of small VC-dimension
scientific article

    Statements

    Shattering-extremal set systems of small VC-dimension (English)
    0 references
    0 references
    0 references
    3 June 2013
    0 references
    Summary: We say that a set system \(\mathcal{F} \subseteq 2^{[n]}\) shatters a given set \(S \subseteq [n]\) if \(2^S = \{F \cap S : F \in \mathcal{F}\}\). The Sauer inequality states that in general, a set system \(\mathcal{F}\) shatters at least \(|\mathcal{F}|\) sets. Here, we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly \(|\mathcal{F}|\) sets. We characterize shattering extremal set systems of Vapnik-Chervonenkis dimension 1 in terms of their inclusion graphs. Also, from the perspective of extremality, we relate set systems of bounded Vapnik-Chervonenkis dimension to their projections.
    0 references
    Vapnik-Chervonenkis dimension
    0 references
    shattering-extremal set systems
    0 references
    Sauer inequality
    0 references

    Identifiers