Discrete Geometry

2022–23–B

Prof. Shakhar Smorodinsky

Course topics

  • 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