Bartosz Walczak
BMS Substitute Professor at TU Berlin
Office MA 502, tel. +493031429400
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):

(19.10.2017) Exercise sheet no. 1 due on 25.10.2017

(26.10.2017) Exercise sheet no. 2 due on 01.11.2017

(02.11.2017) Exercise sheet no. 3 due on 08.11.2017

(09.11.2017) Exercise sheet no. 4 due on 15.11.2017

(16.11.2017) Exercise sheet no. 5 due on 22.11.2017

(30.11.2017) Exercise sheet no. 6 due on 06.12.2017

(08.12.2017) Exercise sheet no. 7 due on 13.12.2017
Lecture topics:

(18.10.2017) The ErdősSzekeres convex polygon problem: the cupscaps theorem, lower bound
[W. Morris, V. Soltan: The ErdősSzekeres problem on points in convex position – a survey] (Section 2)
[J. Matoušek: Lectures on Discrete Geometry] (Section 3.1)

(19.10.2017) The ErdősSzekeres convex polygon problem: Suk's upper bound
[A. Suk: On the ErdősSzekeres convex polygon problem]

(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ősSzekeres 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)

(26.10.2017) Empty convex hexagons (6holes), number of 5holes
[P. Valtr: On the Empty Hexagon Theorem] (Sections 1 and 3)
[O. Aichholzer et al.: A superlinear lower bound on the number of 5holes] (Sections 1–2)

(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)

(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)

(09.11.2017) SzemerédiTrotter incidence bound via cuttings
[J. Matoušek: Lectures on Discrete Geometry] (Sections 4.5 and 4.7)

(15.11.2017) Joints problem, finite field Kakeya problem
[L. Guth: Polynomial Methods in Combinatorics] (Sections 2.1–2.2, 2.4–2.5)

(16.11.2017 and 22.11.2017) SzemerédiTrotter incidence bound via polynomial partitioning
[H. Kaplan, J. Matoušek, M. Sharir: Simple proofs of classical theorems in discrete geometry via the GuthKatz polynomial partitioning technique, available from TUB network] (Sections 1–3)
[L. Guth: Polynomial Methods in Combinatorics] (Sections 10.2–10.4)

(23.11.2017) Distinct distances on two lines
[M. Sharir, A. Sheffer, J. Solymosi: Distinct distances on two lines]

(29.11.2017) ElekesSharir framework, number of krich 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)

(30.11.2017) GuthKatz pointline incidence bound in three dimensions (for 3rich points)
[A. Sheffer: The polynomial method – Lecture notes, Chapter 7] (Theorem 2.4)

(06.12.2017) List coloring of planar graphs, trianglefree Lgraphs with large chromatic number
[M. Aigner, G. Ziegler: Proofs from THE BOOK] (Chapter 25: Fivecoloring plane graphs)
[A. Pawlik et al.: Trianglefree intersection graphs of line segments with large chromatic number] (the same construction presented for segments instead of Lshapes)

(07.12.2017) Planar graphs as Lgraphs
[D. Gonçalves, L. Isenmann, C. Pennarun: Planar graphs as Lintersection or Lcontact graphs] (Sections 2 and 5)

(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 polygoncircle graphs (Section 3)