On the Convexified Sauer–Shelah Theorem

✍ Scribed by Stanislaw J Szarek; Michel Talagrand

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 940 KB
• Volume: 69
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.1736

✦ Synopsis

Let A be a subset of [0, 1] n . Given =>0, we can find a subset I of [1, ..., n] such that the convex hull in R I of the projection of A onto [0, 1] I contains the cube [1Â2&=, 1Â2+=] I , and that card I n&K(n=+-n log(2 n Âcard A)), where K>0 is a universal constant. 1997 Academic Press 1. INTRODUCTION For a subset I of [1, ..., n], let us denote by P I the natural projection from [Sh] asserts that given a subset A of [0, 1] n and an integer k with card A> i k ( n i ), there exists I/[1, ..., n] with card I>k and P I (A)=[0, 1] I . This result has proved to be of considerable use in analysis and probability. One drawback of this result is however the fact that, even when card A 2 n&1 , we cannot guarantee that card I>nÂ2. Moreover, even if, say, card AÂ2 n > .999, it is not, for large n, possible to guarantee that card IÂn .501. Yet it is at times valuable to find subsets I of [1, ..., n] such that n&card I is small, yet P I (A) is ``big.'' One result of this nature and an application was discovered in [S-T], and we introduce the necessary notation to explain this result. For a subset B of [0, 1] I , we denote by conv B the convex hull of B, when B is seen as a subset of R I . We say that B/[0, 1] I is symmetric if