CBMS Conference: Probabilistic and Combinatorial Approach in Analysis

We define the covering numbers of convex bodies and sketch the proofs of two classical inequalities (Dudley's and Sudakov's) relating covering numbers to the supremum of associated Gaussian processes.

We apply methods developed in the previous lecture to modeling a random vector distributed in the convex body. This allows us to give an alternative proof of a result of Bourgain. We also show how these methods lead to an alternative proof of the Uniform Uncertainty Principle of Candes, Romberg and Tao.

We show that any large subset of a discrete cube possesses a certain combinatorial structure. Namely, it has a projection which coincides with a discrete cube of a smaller dimension, called the VC-dimension of the initial subset.

We show how the combinatorial results of the previous lecture can be used to estimate the Banach-Mazur distance from a given convex body to a cube of the same dimension.

We introduce combinatorial dimension, which is an extension of VC-dimension to the non-discrete setting. We discuss the relation between the combinatorial dimension of a set and the probabilistic properties of a random process indexed by this set.

We show that large entropy of a convex body implies the existence of a nice combinatorial structure in it.

We use random coordinate projections to show that the size of the combinatorial structure constructed in the previous lecture is independent of the dimension of the convex body.

We prove that under mild regularity assumptions the entropy of a set is equivalent to its combinatorial dimension. We also solve a long-standing problem of Talagrand concerning estimates of random processes in terms of the combinatorial dimension of the set of parameters.

We show how the combinatorial dimension approach can be applied to extend the Bourgain--Tzafriri restricted invertibility principle for linear operators and to derive a coordinate analog of the classical Dvoretzky theorem in convex geometry.

We establish the relation between the combinatorial dimension of a set and that of its convex hull. We finish with a series of open problems related to combinatorial dimension.