Probabilistic and Algebraic Methods in Combinatorics, Geometry, and Theoretical Computer Science

Instructor Arijit Ghosh

Teaching assistant Gopinath Mishra and Subhabrata Paul

Guest speaker Kunal Dutta from Geometrica, INRIA Sophia Antipolis

Description Study applications of probability and algebraic methods in combinatorics, geometry, and theoretical computer science

Prerequisites Undergraduate course in algorithms, discrete mathematics, probability theory and mathematical maturity

Lecture details

Topics covered in Lecture 1

1. Schwartz-Zippel Lemma: For a proof via induction and probabilistic method refer to [Wiki]. For an algebraic proof using ideas from incidence geometry refer to [M10]. Also read [H12] and [S11].

2. For a proof of Turan's theorem refer to "The Probabilistic Lens: Turan's Theorem" after Chapter 6 from [AS08].

3. Bounding k-sets for a system of disks in the plane via Clarkson-Shor sampling technique refer to the class notes and Section 9.1 of Chapter 9 from [HP11]. Always a good idea to read the original Clarkson-Shor paper [CS89].

Topics covered in Lecture 2

1. Lower bound on crossing number of graphs: Section 9.2 of Chapter 9 from [HP11].

2. Combinatorial Nullstellensatz: Read Sections 1 & 4 from [E11].

3. Also read the papers [A99], [AF93] and [MM10].

Topics covered in Lecture 3

1. Sylvester-Gallai theorem: statement and Kelly's proof. See [Wiki]

2. Vanishing polynomial via linear algebra: Lemma 4 from [E11].

3. Zeev Dvir's proof of "Finite field Kakeya Conjecture": Read [D09] and Section 3 from [E11].

4. Lines and joints problem in 3D: Read Section 3 from [E11]. Also have a look at Section 5 from [GK10] and [KSS10].

Topics covered in Lecture 4

1.Statement of Szemerédi–Trotter Theorem (ST Theorem) bounding incidences $I(P,L)$ between points $P$ and lines $L$ in a plane. See

2. Kovari, Sos and Turan's Theorem (KST Theorem) on excluded $K_{s,t}$-free graphs. See Lecture 8 of [Ceg].

3. Using KST Theorem to get a bound of $O(n^{3/2})$ for the Erdos Unit distance Problem. See Section 2.2.2 from [D12].

4. Using KST Theorem to bound incidences $I(P,L)$ between points $P$ and lines $L$ in a plane. Observe that the bipartite graph obtained from point line incidences is $K_{2,2}$-free.

5. Bounding incidences $I(P,L)$ between points $P$ and lines $L$ in a plane via Cauchy-Schwartz inequality. Read Claim 2.1.2 from Section 2.1 of Chapter 2 from [D12]

6. Szemerédi–Trotter Theorem proof via crossing number lower bound. See Section 2.1.2 of Chapter 2 from [D12] and Section 9.2.2 of Chapter 9 from [HP11].

7. Ham Sandwich Theorem (just statement), Polynomial Ham Sandwich Theorem, and $r$-Partitioning Polynomial method of Guth & Katz. Read Section 2 (all of it) from [KMS12] and Section 2.5 of Chapter 2 from [D12].

Topics covered in Lecture 5

1. Statement of Borsuk-Ulam Theorem, and its use in proving Ham Sandwich Theorems for measures, finite point sets, and general position version. Read Theorem 2.1.1 (just the statement) from Section 2.1 and all of Section 3.1 from [M-BU-08].

2. Proof of Szemerédi–Trotter Theorem using $r$-Partitioning Polynomial method of Guth & Katz. Read Section 3 from [KMS12].

3. Pach-Sharir generalization (just the statement) of Szemerédi–Trotter Theorem for curves. Read Theorem 4.1 from [KMS12].

4. For a set of points P and lines L in the plane. The bound on the number of lines containing more than k points via Szemerédi–Trotter Theorem. See Corollary 2.2.3 from [D12] and Theorem 18.7 from Chapter 18 from Jukna's book on Extremal Combinatorics.

5. Beck's theorem's in combinatorial geometry via Szemerédi–Trotter Theorem. Read Theorem 2.2.4 from [D12].

6. Bound on Erdos unit distance problem via Szemerédi–Trotter Theorem. Read Section 2.2.2 from [D12].

7. Sum product theorem via Szemerédi–Trotter Theorem. Read Section 2.2.3 from [D12].

8. Number of points on a convex curve via Szemerédi–Trotter Theorem. Read Section 2.2.4 from [D12].

Topics covered in Lectures 6, 7, & 8 (by Gopinath Mishra)

1. Fully covered Chapter 5 from [HP11].

Topics covered in Lecture 9

1. Linear-algebraic proof, by Frankl and Pach, of Sauer-Shelah lemma. Read Section 5.2 from [M99].

2. Dudley's weaker version of the Packing Lemma via epsilon-nets, and Chazelle's proof of Haussler's Packing Lemma. Read Section 5.3 from [M99].

Topics covered in Lectures 10 & 11 (Guest lecture by Kunal Dutta)

1. General introduction to VC-dimension, primal shatter dimension, Clarkson-Shor set systems, shallow cell complexity, epsilon-net, and epsilon-sampling theorems. See Sections 5.1, 5.2 and 5.3 from [HP11]. Also read Section 1 from [DGM16].

2. Shallow Packing Lemma statement and proof sketch. See [M16] and [DEG15].

3. Proof of optimal epsilon-net bound via random sampling, Haussler-Welzl's Epsilon-Net Theorem, and shallow packing lemma. See [DGM16].

4. Lower bound of packing number for Clarkson-Shor set systems. See [DGJM16].

5. Definitions of Mnets, and upper bound theorem for Mnets of semi-algebraic set systems in terms of their shallow cell complexity. See [DGJM16].