On the convexified Sauer-Shelah theorem (Q1354724)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the convexified Sauer-Shelah theorem
scientific article

    Statements

    On the convexified Sauer-Shelah theorem (English)
    0 references
    0 references
    0 references
    3 June 1997
    0 references
    Let \(A\) be a subset of \(\{0,1\}^n\). Given \(\varepsilon>0\), we can find a subset \(I\) of \(\{1,\dots,n\}\) such that the convex hull in \(\mathbb{R}^I\) of the projection of \(A\) onto \(\{0,1\}^I\) contains the cube \([1/2-\varepsilon,1/2+\varepsilon]^I\), and that \(\text{card }I\geq n-K(n\varepsilon+\sqrt{n\log(2^n/\text{card }A)})\), where \(K>0\) is a universal constant.
    0 references
    Sauer-Shelah theorem
    0 references
    combinatorial complexity
    0 references

    Identifiers