Math 261C, Probabilistic Combinatorics: Discrete Geometry, Spring 2018

Instructor: Andrew Suk
E-mail: asuk [@] ucsd [dot] edu
Time and Place: APM 7421, MWF 10:00-10:50pm
Office hours: Mon/Wed: 11-12 (after class), and by appointment, APM 6210.
Textbook (optional but recommended): J. Matousek, Lectures on Discrete Geometry.

Course Description: The aim of this course is to give an introduction to discrete geometry and present several results in the field. Topics include: Incidence geometry, Ramsey theory, intersection patterns of geometric objects, graph drawing.

Grades: Homeworks (50%) and oral final exam (50%).


Final Exam Schedule: Sign up here.


Lecture 1 (April 2), Introduction, Sums versus Product.
Lecture 2 (April 4), Crossing Lemma and the Szemeredi-Trotter theorem.
Lecture 3 (April 6), Lower bound for Szemeredi-Trotter.
Lecture 4 (April 9), The cutting lemma.
Lecture 5 (April 11), Simplicial partitionings.
Lecture 6 (April 13), Dense arrangements are locally very dense by Jozsef Solymosi.
Lecture 7 (April 16), Distinct distances and crossing lemma for multigraphs.
Lecture 8 (April 18), Szekely's proof of cn^{4/5} distinct distances. Reference.
Lecture 9 (April 20), Distinct distances on two lines.
Lecture 10 (April 23), Ramsey numbers and tight paths. Reference.
Lecutre 11 (April 25), Shearer's theorem on r(3,n).
Lecture 12 (April 27), Erdos-Szekeres cups/caps theorem.
Lecture 13 (April 30), The Erdos-Rado upper bound argument and r_3(P_s,K_n). Reference.
Lecture 14 (May 2), The Erdos-Rado upper bound arugment: r_3(n,n) < 2^{2^{O(n)}}.
Lecture 15 (May 4), The Erdos-Hajnal stepping up lemma: r_3(n,n,n,n) > 2^{2^{cn}}. Reference for 3 colors.
Lecture 16 (May 7), The Erdos-Hajnal conjecture. Reference.
Lecture 17 (May 9), The Erdos-Hajnal theorem.
Lecture 18 (May 11), The strong Erdos-Hajnal property and intersection graphs of segments in the plane.
Lecture 19 (May 14), Segment intersection graphs are not chi-bounded. Reference. No large independent set Reference.
Lecture 20 (May 16), Dilworth's theorem. Reference.
Lecture 21 (May 18), Circle graphs are chi-bounded. Reference.
Lecture 22 (May 21), Segment disjointness graphs are chi-bounded. Reference.
Lecture 23 (May 23), Maximum number of edges in a convex geometric graph with no k+1 pairwise crossing edges. Reference.
Lecture 24 (May 25), Review.
Lecture 25 (May 30), Finished Lecture 23.
Lecture 26 (Jun 1), k-cross free families.
Final Exams June 4-8.


Homework 1 is here. Hint for problem 1: After applying simplicial partition to obtain P_1,...,P_r, for each line l, if l contains just 1 point in part P_i, throw away that incidence. Then count the rest.