**Topics in Discrete Geometry**

**16:642:587 Selected topics in discrete mathematics**

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

**Instructor:**
Shubhangi Saraf

**Email:** shubhangi.saraf@rutgers.edu

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

**Schedule**

§
**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

§