Topics in Discrete Geometry

16:642:587 Selected topics in discrete mathematics

(Also 16:198:672 Seminar in computer science)




Instructor: Shubhangi Saraf


Timing: Tues, Wed 5 pm – 6:20 pm

Location:  HILL 425

Office hours: Wed 3 pm – 4 pm (Hill 426)

Prerequisites: Basic combinatorics/discrete math, basic linear algebra, mathematical maturity

Text: No required text, however I will be using the following books/surveys as a reference: Incidence Theorems and their Applications (Zeev Dvir) which is available online here, Lectures on Discrete and Polyhedral Geometry (Igor Pak) which is available online here, Lectures on Discrete Geometry (Jiri Matousek), Using the Borsuk-Ulam Theorem (Jiri Matousek)


Description: This course will serve as a graduate topics course in discrete geometry. It will cover a diverse collection of results and techniques in discrete geometry and incidence geometry spanning a wide range of topics, including some of the classical gems as well as some of the more recent results.


The following is a partial and tentative list of topics:

·      Convexity and applications (Helly’s theorem, Caratheodory’s theorem, Barany’s theorem)

·      Line-point incidence theorems and applications

·      Topological methods (applications of the Borsuk-Ulam theorem)

·      The Polynomial method and applications (Distinct distances, joints conjecture, Kakeya type problems)

·      Metric embeddings


Homework: Problem sets will be posted every 2-3 weeks.

Homework 1




§  Lecture 1 (Tues 01/21): Cancelled due to snowstorm

§  Lecture 2 (Wed 01/22): Administrative details, course overview, start convexity

§  Lecture 3 (Tues 01/28):  Caratheodory’s Theorem, Radon’s theorem, Helly’s theorem

§  Lecture 4 (Wed 01/29):  Fractional Helly, Sylverster-Gallai, Colorful Caratheodory

§  Lecture 5 (Tues 02/04):  Tverberg’s theorem, Barany’s theorem, centerpoint theorem

§  Lecture 6 (Wed 02/05):  Hilbert’s third problem, line-point incidences