Bartosz Walczak

BMS Substitute Professor at TU Berlin

Office MA 502, tel. +49-30-314-29400


Combinatorial geometry

Lectures: Wednesdays 10:15–11:45 in MA 549, Thursdays 10:15–11:45 in MA 550

Exercise sessions: Wednesdays 8:30–10:00 in MA 549

Abstract: Questions in combinatorial geometry typically involve finite sets of points, lines, circles, planes, or other simple geometric objects. Despite these simple ingredients, the field offers a wealth of challenging problems. Efforts to their solution lead to a rich collection of methods which also borrows from other fields, such as probabilistic and algebraic arguments. This course offers a thorough introduction to combinatorial geometry with particular focus on recent results and open (as yet unsolved) problems.

Exercise sheets (please have your solutions prepared for oral presentation during the exercise sessions):

  1. (19.10.2017) Exercise sheet no. 1 due on 25.10.2017
  2. (26.10.2017) Exercise sheet no. 2 due on 01.11.2017
  3. (02.11.2017) Exercise sheet no. 3 due on 08.11.2017
  4. (09.11.2017) Exercise sheet no. 4 due on 15.11.2017
  5. (16.11.2017) Exercise sheet no. 5 due on 22.11.2017
  6. (30.11.2017) Exercise sheet no. 6 due on 06.12.2017
  7. (08.12.2017) Exercise sheet no. 7 due on 13.12.2017

Lecture topics:

  1. (18.10.2017) The Erdős-Szekeres convex polygon problem: the cups-caps theorem, lower bound
    [W. Morris, V. Soltan: The Erdős-Szekeres problem on points in convex position – a survey] (Section 2)
    [J. Matoušek: Lectures on Discrete Geometry] (Section 3.1)
  2. (19.10.2017) The Erdős-Szekeres convex polygon problem: Suk's upper bound
    [A. Suk: On the Erdős-Szekeres convex polygon problem]
  3. (25.10.2017) Suk's upper bound (remaining part), empty convex polygons, Horton sets
    [A. Pór, P. Valtr: The partition version of the Erdős-Szekeres theorem, available from TUB network] (Theorem 4)
    [J. Matoušek: Lectures on Discrete Geometry] (Section 3.2)
    [H. Harborth: Konvexe Fünfecke in ebenen Punktmengen] (voluntary additional reading)
  4. (26.10.2017) Empty convex hexagons (6-holes), number of 5-holes
    [P. Valtr: On the Empty Hexagon Theorem] (Sections 1 and 3)
    [O. Aichholzer et al.: A superlinear lower bound on the number of 5-holes] (Sections 1–2)
  5. (01.11.2017 and 02.11.2017) Arrangements (by Stefan Felsner)
    [J. Matoušek: Lectures on Discrete Geometry] (Sections 6.1–6.2)
    [S. Felsner: Geometric Graphs and Arrangements] (Propositions 5.3–5.4, 5.13–5.14)
  6. (08.11.2017) Incidence bounds via crossing number
    [J. Matoušek: Lectures on Discrete Geometry] (Section 4.1, Proposition 4.2.1, Sections 4.3–4.4)
  7. (09.11.2017) Szemerédi-Trotter incidence bound via cuttings
    [J. Matoušek: Lectures on Discrete Geometry] (Sections 4.5 and 4.7)
  8. (15.11.2017) Joints problem, finite field Kakeya problem
    [L. Guth: Polynomial Methods in Combinatorics] (Sections 2.1–2.2, 2.4–2.5)
  9. (16.11.2017 and 22.11.2017) Szemerédi-Trotter incidence bound via polynomial partitioning
    [H. Kaplan, J. Matoušek, M. Sharir: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, available from TUB network] (Sections 1–3)
    [L. Guth: Polynomial Methods in Combinatorics] (Sections 10.2–10.4)
  10. (23.11.2017) Distinct distances on two lines
    [M. Sharir, A. Sheffer, J. Solymosi: Distinct distances on two lines]
  11. (29.11.2017) Elekes-Sharir framework, number of k-rich points in three dimensions
    [A. Sheffer: The polynomial method – Lecture notes, Chapter 6] (Section 2)
    [A. Sheffer: The polynomial method – Lecture notes, Chapter 7] (Section 1, Corollary 2.5)
  12. (30.11.2017) Guth-Katz point-line incidence bound in three dimensions (for 3-rich points)
    [A. Sheffer: The polynomial method – Lecture notes, Chapter 7] (Theorem 2.4)
  13. (06.12.2017) List coloring of planar graphs, triangle-free L-graphs with large chromatic number
    [M. Aigner, G. Ziegler: Proofs from THE BOOK] (Chapter 25: Five-coloring plane graphs)
    [A. Pawlik et al.: Triangle-free intersection graphs of line segments with large chromatic number] (the same construction presented for segments instead of L-shapes)
  14. (07.12.2017) Planar graphs as L-graphs
    [D. Gonçalves, L. Isenmann, C. Pennarun: Planar graphs as L-intersection or L-contact graphs] (Sections 2 and 5)
  15. (13.12.2017) Coloring rectangle graphs and circle graphs
    [E. Asplund, B. Grünbaum: On a coloring problem] (Section 3)
    [C. Hendler: Schranken für Färbungs- und Cliquenüberdeckungszahl geometrisch repräsentierbarer Graphen] (Section 6.3 – voluntary additional reading)
    [A. Kostochka, J. Kratochvíl: Covering and coloring polygon-circle graphs (Section 3)