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

Exercise sheet no. 1 due on 25.10.2017

Exercise sheet no. 2 due on 01.11.2017

Exercise sheet no. 3 due on 08.11.2017

Exercise sheet no. 4 due on 15.11.2017

Exercise sheet no. 5 due on 22.11.2017

Exercise sheet no. 6 due on 06.12.2017

Exercise sheet no. 7 due on 13.12.2017

Exercise sheet no. 8 due on 20.12.2017

Exercise sheet no. 9 due on 10.01.2018 and 17.01.2018

Exercise sheet no. 10 due on 24.01.2018

Exercise sheet no. 11 due on 31.01.2018 and 14.02.2018
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)
[A. Sheffer: The polynomial method – Lecture notes, Chapter 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)

(14.12.2017) Coloring outerstring graphs
[A. Rok, B. Walczak: Outerstring graphs are χbounded]

(20.12.2017) Coloring outerstring graphs (continued), number of edges in kquasiplanar graphs
[A. Rok, B. Walczak: Outerstring graphs are χbounded]
[A. Suk, B. Walczak: New bounds on the number of edges in kquasiplanar graphs] (Sections 2 and 6)

(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 kquasiplanar graphs] (Lemma 3.2)

(10.01.2018 and 11.01.2018) Recap of some previous topics

(17.01.2018) Number of edges in 3quasiplanar 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)

(18.01.2018) Weak perfect graph theorem
[J. Matoušek: Lectures on Discrete Geometry] (Section 12.1)

(24.01.2018 and 25.01.2018) VCdimension and εnets
[J. Matoušek: Lectures on Discrete Geometry] (Section 10.2)

(31.01.2018 and 01.02.2018) εNets for halfspaces, lower bound for εnets
[S. HarPeled et al.: εNets for halfspaces revisited] (Section 2, first proof)
[J. Pach, G. Tardos: Tight lower bounds for the size of epsilonnets, available from TUB network] (Section 2)

(14.02.2018) Weak εnets for convex sets, fractional Helly theorem, HadwigerDebrunner (p, q)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)

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