Watch the following videos before the lecture on Tuesday, October 25:

• 1-Radon: Convex sets, Radon's theorem. (Ref: M 1.2 and M 1.3)
  https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=a2c58fca-c21a-4ffe-94cd-adb900aff564&instance=HUJI21
• 2-Helly: Helly's theorem and application to center points. (Ref: M 1.3)
  https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=4c8f1207-2df0-499e-b96b-adb900b66e2e&instance=HUJI21
• 3-Tverberg, Separation, Caratheodory: Tverberg's theorem, Separation lemma, Caratheodory's theorem. (Ref: M 8.3 and M 1.2)
  https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=b0f982f8-daa1-47e4-b51e-adb900bf25b9&instance=HUJI21

Watch the following videos before the lecture on Tuesday, November 01:

• 4-Caratheodory, cone and colorful: Proof of Caratheodory's theorem (via a cone version), Barany's theorem ("colorful Caratheodory").
  (Ref: M 8.2)
  Typo: in the cone version thm, 6th minute, we are missing the b_i's in the representation of a or (a-t_0), namely: Sum(alpha_i-tbeta_i)b_i instead of Sum(alpha_i-t beta_i).
  https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=a1b916f0-fc6b-4e32-99c6-adb900c63e30
• 5-Tverberg, proof: Proof of Tverberg's theorem. (Ref: M 8.3)
  Typo: missing: a_i = (v_i, 1- (sum of coordinates of v_i)).
  https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=c4c4e957-c47b-477c-9591-adbd006d9328

Watch the following videos before the lecture on Tuesday, November 08:

• Points and lines -- https://www.youtube.com/watch?v=um92hUfJfJY
• Sumset estimates -- https://www.youtube.com/watch?v=dy3jAo5SZPA
• Euler's formula -- https://www.youtube.com/watch?v=AHiuPj7A2TY

This year (WiSe 22/23), the course is organized together with the Hebrew University of Jerusalem. We hope to connect students from both Universities.

The lecturers Christian Haase, and Eran Nevo will provide video lectures. Those will be discussed in hybrid (i.e., synchronized in person and online) Q&A sessions on Tuesdays (10-12). 

Exercise sessions will take place on Wednesdays (8-10) and are meant to facilitate discussions and interaction among students. Those will be online and guided by Sophie Rehberg.

During the course we will use a different platform (moodle) provided by the Hebrew University in Jerusalem. You will get access as soon as possible, please make sure you are registered in the Whiteboard.

This year the course will cover the following topics:

• Radon's lemma, Helly's theorem, centerpoints, colorful Caratheodory theorem, Tverberg's theorem
• Euler's formula, crossing numbers, amplification through probabilistic method, Szemeredi-Trotter theorem, applications to sum-product estimates
• Unit distances problem, distinct distances, Erdos-Szekeres theorem via hypergraph Ramsey theory, number of joints via polynomial method
• Polytopes and polyhedra, Minkowski-Weyl theorem, Steinitz' theorem
• Balinksi's theorem, Hirsch conjecture, (possibly vertex-decomposibility)
• Neighborly, cyclic, stacked polytopes, f-vectors, Dehn-Sommerville relations, shellability, upper bound theorem
• Gale duality, non-rational polytopes
• matroids, matroid polytopes
• Triangulations, Voronoi and Delaunay, the associahedron

Das ist die erste Vorlesung in einem Zyklus von drei Vorlesungen in diskreter Geometrie. Das Ziel dieser Vorlesung ist es, mit diskreten Strukturen und verschiedenen Beweistechniken vertraut zu werden. Der Inhalt wird aus einer Auswahl aus den folgenden Themen bestehen:

Polyeder und polyedrische Komplexe
Konfigurationen von Punkten, Hyperebenen und Unterräumen
Unterteilungen und Triangulierungen
Theorie von Polytopen
Darstellungen und der Satz von Minkowski-Weyl
Polarität, einfache und simpliziale Polytope, Schälbarkeit
Schälbarkeit, Seitenverbände, f-Vektoren, Euler- und Dehn-Sommerville Gleichungen
Graphen, Durchmesser, Hirsch Vermutung
Geometrie linearer Programmierung
Lineare Programme, Simplex-Algorithmus, LP Dualität
Kombinatorische Geometrie, geometrische Kombinatorik
Arrangements von Punkten und Geraden, Sylvester-Gallai, Erdös-Szekeres
Arrangements, Zonotope, zonotopale Kachelungen, orientierte Matroide
Beispiele, Beispiele, Beispiele
Reguläre Polyope, zentralsymmetrische Polytope
Extremale Polytope, zyklische/nachbarschaftliche Polytope, gestapelte Polytope
Kombinatorische Optimierung und 0/1-Polytope
 

Literatur

• G.M. Ziegler "Lectures in Polytopes"
• J. Matousek "Lectures on Discrete Geometry"
• Further literature will be announced in class.

Zusätzliche Informationen

Gute Kenntnisse der linearen Algebra werden vorausgesetzt. Vorbildung in Kombinatorik und Geometrie sind hilfreich.