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.
- Basic notions of convexity; the theorems of Helly, Radon and Caratheodory.
- Geometric constructions and proofs in number theory: additive structures, the sum-product problem, arithmetic progressions.
- Structure of convex sets, different representations of volume.
- Geometric duality and polarity, basics of linear programming.
- Volumes of convex bodies: the Brunn-Minkowski inequality, isoperimetric inequalities.
- Concentration estimates on the sphere, geometric applications.
- Approximation by ellipsoids, Fritz John's theorem.
- Sections of convex bodies, Dvoretzky's theorem.
- Embedding of metric spaces, the Johnson-Lindenstrauss lemma.
- Structure of frames, decompositions of the identity.
- Plank problems and arrangements of unit vectors.