- Fundamental theorems and basic definitions:
Convex sets, separation , Helly’s theorem, fractional Helly, Radon’s theorem, Caratheodory’s theorem, centerpoint theorem. Tverberg’s theorem. Planar graphs. Koebe’s Theorem.
- Geometric graphs: the crossing lemma.
Application of crossing lemma to Erdos problems:
Geometric Incidences, Repeated distance problem, distinct distances problem. Selection lemmas. Counting $k$-sets. An application of incidences to additive number theory.
- Coloring and hiting problems for geometric hypergraphs : $VC$-dimension, Transversals and Epsilon-nets. Weak eps-nets for convex sets. $(p,q)$-Theorem, Conflict-free colorings.
- Arrangements : Davenport Schinzel sequences and sub structures in arrangements.
- Geometric Ramsey and Turan type theorems: Application of Dilworth theorem, Erdos-Szekeres theorem for convex sets, quasi-planar graphs.
University course catalogue: 201.2.0191