On the convexified Sauer-Shelah theorem (Q1354724): Difference between revisions

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.