Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

One of the classical problems of theory of random processes is "describe classes of functions for which the limit theorems of probability hold uniformly". It was noticed early that the problem is intimately connected with a combinatorics of the class. This gave rise to the concept of Vapnik-Chervonenkis dimension or, in general, the "combinatorial dimension", which is widely used in logic, computer science, convex and discrete geometry and, of course, probability and combinatorics. There exists a remarkable description of the classes for which the Law of Large Numbers holds (this was so-called Glivenko-Cantelli problem). However, the situation with the other classical theorem of probability, the Central Limit Theorem, has been much less satisfactory. Jointly with Mark Rudelson of the University of Missouri-Columbia, we recently completed the solution to the basic conjecture: "CLT holds uniformly on F if the square root of the combinatorial dimension of F is integrable." In this talk, I will describe the fascinating concept of the combinatorial dimension and indicate its use in different areas, and how it connects combinatorics and probability.