[MPI-Logo] [Uni-Logo]


Discrete Geometry

Advanced lecture in Summer 2009

In this course we aim to give an introduction to discrete geometry and present some of the recent results in this area. We will look at several fundamental and beautiful results on combinatorial properties of geometric objects many of which are motivated by applications in other areas. The course has no prerequisite except very basic combinatorics and probability theory.



Instructors: Saurabh Ray and Rajiv Raman
Lectures: Wed 16-18 in MPI 3rd Floor rotunda
Exercises: Thu 12:05-13:00
Credit: This is an advanced course with 6 credit points.
Prerequisites: Basic combinatorics and probability theory
Course  Material: Most of the material will be from the book Lectures in Discrete Geometry by J.Matousek and recent research papers. Another good reference is Combinatorial Geometry by J. Pach and P.K. Agarwal.

Course Contents:

The main topics covered in the course will be: Helly's Theorem, Fractional Helly Theorem, Centerpoint Theorem, Ham-Sandwich Theorem, Geometric Selection Theorems, Weak Epsilon Nets and Topological Methods for proving combinatorial results.

Lectures

Date
 		Topic
 		Exercise
27.04.09
Centerpoint Theorem, Helly's Theorem, Ham-Sandwich Theorem
ex1.pdf
06.05.09
 Fractional Helly's Theorem, Caratheodory's Theorem
 ex2.pdf
13.05.09
 Colorful Caratheodory Theorem, First Selection Lemma, Weak Epsilon Nets
 ex3.pdf
20.05.09
 More Weak Epsilon Nets: Improved bounds in the plane
 ex4.pdf
27.05.09
 Sperner Lemma, Brouwer's fixed point theorem
03.06.09
 Sperner <=> Brouwer , KKM Lemma
10.06.09
 Intersecting Convex Sets with Rays : Application of Brouwer's Fixed Point Theorem
17.06.09
 Borsuk Ulam Theorem <=> Tucker Lemma
19.06.09
 Equivalent statements of Borsuk Ulam Theorem and Proof of Ham Sandwich Theorem in General Dimensions
22.07.09 Proof of Tucker Lemma
24.07.09
 Introduction to Sarkaria's technique and Proof of Tverberg's theorem
29.07.09 More on Sarkaria's Technique: Kirchberger's Theorem and its Multipartite version ex6.pdf