Discrete Geometry

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

The course is intended for 3rd year undergraduate as well as M.Sc and Ph.D. students both in computer science and mathematics. We will touch main topics in the area of discrete geometry. Some of the topics are motivated by the analysis of algorithms in computational geometry, wireless and sensor networks. Some other beautiful and elegant tools are proved to be powerful in seemingly non-related areas such as additive number theory or hard Erdos problems. The course does not require any special background except for basic linear algebra, and a little of probability and combinatorics. During the course many open research problems will be presented.

Detailed Syllabus:

• Fundamental theorems and basic definitions: Convex sets, convex combinations, separation , Helly’s theorem, fractional Helly, Radon’s theorem, Caratheodory’s theorem, centerpoint theorem. Tverberg’s theorem. Planar graphs. Koebe’s Theorem. A geometric proof of the Lipton-Tarjan separator theorem for planar graphs.
• Geometric graphs: the crossing lemma. Application of crossing lemma to Erdos problems: Incidences between points and lines and points and unit circles. Repeated distance problem, distinct distances problem. Selection lemmas for points inside discs, points inside simplexes. 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. Conflict-free colorings .
• Arrangements : Davenport Schinzel sequences and sub structures in arrangements. Geometric permutations.
• Geometric Ramsey and Turan type theorems: Application of Dilworth theorem, Erdos-Szekeres theorem for convex sets, quasi-planar graphs.