Convexity

Lecturer

Prof. Friedrich Eisenbrand

Assistant

Christoph Hunkenschröder

News & Log

22.09.: Convex Sets, Theorems of Caratheodory, Radon, Helly, Chap. 1.2, 1.3 in Matousek; introduction to lattices, Minkowski’s first theorem, Chap. 2.1, 2.2 in the same book

29.09.: Minkowski’s second theorem, Chap. 1.8 in the lecture notes of Thomas Rothvoß; John’s theorem, Chap. 2.1 in the lecture notes of Thomas Rothvoß

06.09.: Dual Lattices and the Flatness Theorem, Chap. 7 & 8 in Barvinok

There was no lecture and no class on October 13, 2016

20.10.: Continuing Flatness Theorem and equivalence of finitely generated and polyhedral cones

27.10.: Continuing on cones, in particular the Minkowski-Weyl Theorem, Introduction of Voronoi cells

03.11.: Affine hull, dimensions of polyhedra, faces and facets, limiting the number of facets of a Voronoi cell, cf. Schrijver

10.11.: The CVP algorithm via Voronoi Cells of Vicciancio and Voulgaris

17.11.: The LLL algorithm

24.11.: The volume of the unit ball and Gaussians, volumes of polyhedra

01.12.: Brunn’s inequality and the Brunn-Minkowski inequality, cf. Matousek

08.12.: Concentration of Measure on the Sphere, Random Projections

15.12.: Random Projections, Gaussian Annulus Theorem, Johnson-Lindenstrauss Theorem

Description

Convexity is a fundamental concept in mathematics. This course is an introduction to convexity and its ramifications in high-dimensional Geometry.

Here you can find out more about the course.

Schedule

Lecture: Thursday 14:15 – 16:00 (INM 203);
Exercises: Thursday 16:15 – 18:00 (INM 203);

Office hours: Wednesday 11:00 – 12:00 (MA C1 573)

Final Exam

The final written exam will take place on Monday, January 16, 2017 from 8:15 to 11:15 (please be there on time) in room CE1101.

You can view your exam on Thursday, Feburary 9, 2017 at 14:00 in room MA B1 524.

Grading

Your grade will be determined by a written exam during an exam session. You can collect bonus points by handing in solutions to selected exercises from the assignment sheets. If you score an average of 50% or more in the exercises, the grade of your final exam will be improved by a half grade. If you score an average of 90% or more, the grade of your final exam will be improved by a full grade. The bonus points will be awarded only to students who get a grade of at least 4 in the exam.

Assignments

We will publish an assignment sheet with problems and practical exercises on the webpage every week before the lecture. You can work on the exercises, ask questions, and discuss problems during the exercise sessions. You will have the opportunity to hand in written solutions for feedback.

Correct solutions to selected “star” problems give you bonus points. The deadline is one week after the sheet is issued. More precisely, you can either hand in the solutions to the assistant during the exercise session, or leave your solutions in the box next to MA C1 573 (be sure to put them in the correct box) or send them via email by 14:00 on Thursday.

Star-exercises can be handed in by groups of up to 3 people.

The following questions are thought to give you help by reviewing the topics of the lecture. They do not aim to cover the whole lecture, but rather give you an idea on the kind of questions you could have in mind when repeating the content of the course.

Literature

  1. Jiri Matousek, Lectures on Discrete Geometry.
  2. Thomas Rothvoß, Integer Optimization and Lattices, Lecture notes (https://www.math.washington.edu/~rothvoss/583D-spring-2016/IntOpt-and-Lattices.pdf)
  3. Alexander Barvinok, A Course in Convexity.
  4. Jiri Matousek, Metric Embeddings, Lecture notes (http://kam.mff.cuni.cz/~matousek/ba-a4.pdf)