Instructor: Dr. Gergely AMBRUS
Text: Classnotes by the lecturer, based on recent articles and the book .Lectures on Discrete Geometry. by J. Matou.ek.
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 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 be always explained.
Course description: In the last century, the ancient subject of convex geometry has undergone a major revival. One the one hand, the birth of discrete geometry (which happened here in Budapest) provided extensive links to combinatorics and probability. On the other hand, the geometry of higher dimensional Euclidean spaces turned out to be surprisingly different from our lower dimensional intuition, which further implied crucial results related to embeddings of metric spaces and the geometry of Banach spaces. The rapidly emerging field of Computer Science unites these topics: many important problems therein lead to purely geometric questions. We are going to cover topics that are perhaps the most beautiful and useful in this broad subject, concentrating mainly on the combinatorial and analytic side. En route, we will constantly shed light on the underlying interplay between geometry, probability, linear algebra, analysis, and combinatorics.
Topics:
Basic notions of convexity; the theorems of Helly, Radon and Caratheodory.
Results from combinatorial convex geometry: the Erd.s-Szekeres theorem, problems regarding unit distances and incidences.
Geometric constructions and proofs in number theory: additive structures, the sum-product problem, arithmetic progressions.
Plank problems, arrangements of unit vectors, applications in functional analysis.
Volumes of convex bodies: the Brunn-Minkowski inequality, isoperimetric inequalities.
Duality and polarity, basics of linear programming.
High dimensional convex geometry: volume estimates, concentration phenomena, Dvoretzky.s theorem, Johnson-Lindenstrauss lemma.
Approximation by ellipsoids, Fritz John.s theorem.
Geometric problems in Computer Science.