Incidence Geometry and Its Applications (Summer students programme, 2018)

Instructor  Arijit Ghosh

Description A brief introduction to Incidence Geometry

Intended Audience TCS summer students at IMSC

Lecture details

Topics covered in Lecture 1

• Statements of Szemeredi-Trotter (ST) theorem and Pach-Sharir's refinement of ST Theorem. 

• Applications of ST:

  • • Bounding the number of heavy lines.

    • Beck's Ramsey-type result for points and lines in 2D. 

    • Elekes's Sum-Product estimate using ST. 

    • Erdos's Unit Distance estimate using ST.

• Lower bound on Erdos's distinct distance problem using Landau-Ramanujan Constant [LR].

• Reading materials:

  • • Sections 2.1 and 2.2 from Chapter 2 of [D12].

    • Read [LR].

Topics covered in Lecture 2

• Number of lattice points on a Convex Curve in 2D via ST theorem.

• Statement of Guth-Katz's Polynomial Partitioning Theorem. 

• Existence of low degree of polynomials vanishing on a finite set in d-dimensional Euclidean space.

• Statement of Ham-Sandwich Theorem.

• Statement and Proof of Polynomial Ham-Sandwich Theorem.

• Simple properties of polynomials. 

• Reading materials:

  • • Sections 2.5 from Chapter 2 of [D12].

    • Sections 1 and 2 from [KMS12].

Topics covered in Lecture 3

• Proof of ST Theorem using Polynomial Partitioning Theorem.

• Proof of Polynomial Partitioning Theorem using Polynomial Ham-Sandwich Theorem.

• Reading materials:

  • • Section 4 of [I08].

    • Sections 2.5 from Chapter 2 of [D12].

    • Sections 1 and 2 from [KMS12].

Topics covered in Lecture 4

• Basic properties of planar graphs. 

• Proof of Crossing Lemma via the probabilistic method. 

• Proof of ST Theorem via Crossing Lemma. 

• Reading materials:

  • • Sections 2.5 from Chapter 2 of [D12].

    • Sections 1 and 2 from [KMS12].