Bartosz Walczak

BMS Substitute Professor at TU Berlin

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

Homepage

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. Exercise sheet no. 1 due on 25.10.2017
  2. Exercise sheet no. 2 due on 01.11.2017
  3. Exercise sheet no. 3 due on 08.11.2017
  4. Exercise sheet no. 4 due on 15.11.2017
  5. Exercise sheet no. 5 due on 22.11.2017
  6. Exercise sheet no. 6 due on 06.12.2017
  7. Exercise sheet no. 7 due on 13.12.2017
  8. Exercise sheet no. 8 due on 20.12.2017
  9. Exercise sheet no. 9 due on 10.01.2018 and 17.01.2018
  10. Exercise sheet no. 10 due on 24.01.2018
  11. Exercise sheet no. 11 due on 31.01.2018 and 14.02.2018

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)
    [A. Sheffer: The polynomial method – Lecture notes, Chapter 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)
  16. (14.12.2017) Coloring outerstring graphs
    [A. Rok, B. Walczak: Outerstring graphs are χ-bounded]
  17. (20.12.2017) Coloring outerstring graphs (continued), number of edges in k-quasi-planar graphs
    [A. Rok, B. Walczak: Outerstring graphs are χ-bounded]
    [A. Suk, B. Walczak: New bounds on the number of edges in k-quasi-planar graphs] (Sections 2 and 6)
  18. (21.12.2017) Separators in planar graphs, decomposable subfamilies of curves
    [J. Erickson: Computational topology, Chapter 10: Graph separators] (Section 10.1)
    [W. McCuaig: A simple proof of Menger's theorem, available from TUB network] (voluntary additional reading)
    [J. Fox, J. Pach, A. Suk: The number of edges in k-quasi-planar graphs] (Lemma 3.2)
  19. (10.01.2018 and 11.01.2018) Recap of some previous topics
  20. (17.01.2018) Number of edges in 3-quasi-planar graphs, number of crossings in realizations of string graphs
    [J. Pach, R. Radoičić, G. Tóth: Relaxing planarity for topological graphs] (Section 7)
    [J. Matoušek: String graphs and separators] (Section 4)
  21. (18.01.2018) Weak perfect graph theorem
    [J. Matoušek: Lectures on Discrete Geometry] (Section 12.1)
  22. (24.01.2018 and 25.01.2018) VC-dimension and ε-nets
    [J. Matoušek: Lectures on Discrete Geometry] (Section 10.2)
  23. (31.01.2018 and 01.02.2018) ε-Nets for half-spaces, lower bound for ε-nets
    [S. Har-Peled et al.: ε-Nets for halfspaces revisited] (Section 2, first proof)
    [J. Pach, G. Tardos: Tight lower bounds for the size of epsilon-nets, available from TUB network] (Section 2)
  24. (14.02.2018) Weak ε-nets for convex sets, fractional Helly theorem, Hadwiger-Debrunner (pq)-problem
    [N. Alon et al.: Point selections and weak ε-nets for convex hulls] (Section 9)
    [J. Matoušek: Lectures on Discrete Geometry] (Sections 8.1 and 10.5)
  25. (15.02.2018) Halving lines
    [J. Matoušek: Lectures on Discrete Geometry] (Lemma 11.3.1 and Section 11.4)
    [G. Nivasch: An improved, simple construction of many halving edges]