Geometric Combinatorics, Easter 2010

When:

Mondays, Wednesdays, Fridays 10am

Where:

MR4, CMS

What:

This short lecture course will focus on a selection of topics from geometric combinatorics. We shall discuss combinatorial convexity theorems of Helly, Carathéodory, Tverberg and their relatives, geometric discrepancy and VC-dimension, and Szemerédi–Trotter theorem.

Resources:

The book Lectures on Discrete Geometry by Jiří Matoušek is easily the best introduction to discrete geometry. Most of the material that we will cover is in the book. A copy is on reserve in the library. Another worthy book is Lectures on Discrete and Polyhedral Geometry by Igor Pak. It is a great read, but overlaps with the content of this course much less. It is available freely from the author's webpage. The material on discrepancy is mostly from Geometric discrepancy (An illustrated guide) by Matoušek, and Discrepancy method by Bernard Chazelle. A PDF of the latter book is on the author's webpage.

Lectures:

Note that there will be no lecture on May 19 due to a One-Day Colloquim in Combinatorics in London.

• April 23: Helly and Carathéodory theorems, centrepoints. Example sheet #1.
• April 26: Jung's theorem, fractional Helly theorem. Supplementary notes #1.
• April 28: Colourful Carathéodory, Tverberg's theorem, “first selection theorem”.
• April 30: VC-dimension, ε-nets. Example sheet #2
• May 3: ε-approximations, spaces of bounded VC-dimension, weak ε-nets.
• May 5: Weak ε-nets (cont'd), (p,q)-theorem. Supplementary notes #2 and example sheet #3.
• May 7: Discrepancy of axis-parallel boxes.
• May 10: Discrepancy of axis-parallel boxes (cont'd).
• May 12: Combinatorial discrepancy and VC-dimension. Supplementary notes #3.
• May 14: Combinatorial discrepancy and VC-dimension (cont'd).
• May 17: Szemerédi–Trotter theorem, a sum-product estimate.
• May 19: One-Day Colloquim in Combinatorics, Queen Mary, London.