Instructor: Dr. Gergely AMBRUS

Text: Classnotes by the lecturer, based on recent articles and the book "Lectures on Discrete Geometry" by J. Matousek.

Prerequisite: General mathematical experience of the undergraduate level is expected. In particular, we are going to use the contents of a first course in linear algebra, a first course in probability and measure theory and a real analysis course. It is beneficial, though not crucial, to know the basic concepts of convex geometry, and it is essential to be familiar with the Euclidean spaces R^n. To keep everyone aboard, the basic notions and concepts will always be explained.

Course description: In the last century, the ancient subject of convex geometry has undergone a major revival, and it found applications in the recent fields of theoretical computer science, cryptography, motion planning and so on. We are going to cover topics that are perhaps the most beautiful and useful for these applications, concentrating mainly on the combinatorial and analytic side. At the beginning of the course, we study the essential notion of convexity, and discuss some beautiful results from discrete geometry, with connections to combinatorics. After that we quickly move on towards higher dimensional Euclidean spaces, whose geometry turns out to be surprisingly different from our lower dimensional intuition. Exploiting this peculiar behaviour will let us prove powerful results about concentration of functions, metric embeddings, geometric inequalities. The main goal is to prove the strong theorems of John, Dvoretzky, Johnson and Lindenstrauss, which become the building blocks of modern day computer science.

Topics: