### 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.