Table of Content

Diskrete Geometrie II

Sommersemester 2018
Stefan Felsner

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 26 , 27

1. Vorlesung, Mi. 18.4.2018 

    Helly Type Theorems
       Helly 1, Helly 2 und Satz von Helly
       Satz von Radon
       Ein Helly-Äquivalent für Translate
2. Vorlesung, Do. 19.4.2018 
      Fraktionales Helly Theorem
         Morse Funktion
      Triangulierung von Polytopen
      Satz von Caratheodory
3. Vorlesung, Mi. 25.4.2018 
         Distanzargumente: Sylvester-Gallai ordinary lines
         Colorful Caratheodory
      Tverberg Problem
          (ein Artikel zur Geschichte: Ziegler 2011)
         Submultiplikativität von T(d,r)
         Eine Schranke an T(d,r)
      Barany Theorem
4. Vorlesung, Do. 26.4.2018 
      Centerpoint Theorem
         3N Punkte und N Dreiecke (Birch)
         4 flächengleiche Teile mit 2 orthogonalen Geraden
         Anwendung: Halfspace range searching
5. Vorlesung, Mi. 2.5.2018 
      Ham-Sandwich Cuts
         Diskreter HS-Satz
         HS-Satz für Maße
            Satz von Borsuk-Ulam
      Dualität
         Dualität auf der Sphäre
6. Vorlesung, Do. 3.5.2018 
         Polarität am Einheitskreis
         Polarität an der Parabel
     HS-Satz in 2D mit dualen Arrangements
 Die Borsuk Vermutung
     Borsuk für glatte, konvexe Körper
7. Vorlesung, Mi. 9.5.2018 
     Das Kahn-Kalai Gegenbeispiel
        Kombinatorialisierung: (n,k,t)-Familien
        Satz von Frankl und Wilson
        Konstuktion mit balancierten Schnitten
8. Vorlesung, Mi. 16.5.2018 
     Die chromatische Zahl des Rn
        Die chromatische Zahl der Ebene ist 5, 6 oder 7
        χ(Rn) wächst exponentiell in n
 Polytope
     V- und H-Polytope	
        Dualität (Polarität) von Polytopen
9. Vorlesung, Do. 17.5.2018 
       V- und H-Polytope sind dasselbe
    Seiten und f-Vektoren  
       Der Seitenverband
       f-Vektoren und Euler-Poincare Formel
10. Vorlesung, Mi. 23.5.2018 
       Dehn-Sommerville Gleichungen für einfache Polytope
       h-Vektor und in-degrees
    Zyklische Polytope
       Gale's evenness condition
11. Vorlesung, Do. 24.5.2018 
       Zyklische Polytope sind nachbarschaftlich 
       Upper Bound Theorem
    Unique Sink Orientations (USO)
       Kleinste einschließende Bälle
12. Vorlesung, Mi. 30.5.2018 
       Unique Sink Orientations von Würfeln
          Out-map ist injektiv
          T(n) < T(n-k)T(k) und T(n) < 1,71^n
13. Vorlesung, Do. 31.5.2018 
          Die Fibonacci Wippe
          Verbesserung durch Randomisierung
   Konvexe Polygone in planaren Punktmengen
      Happy Ending Problem
      Erdős-Szekeres Theorem
      Ähnliche Probleme
         Ramsey Theory
         Erdős-Szekeres: Monotone Teilfolgen
         Dilworth: Ketten und Antiketten
14. Vorlesung, Mi. 6.6.2018 
      Beweis Erdős-Szekeres Theorem
         Obere Schranke (k-caps und k-cups)
         Untere Schranke (Konstruktion)
      Verbesserungen der obere Schranke
      Suk's Theorem
         Anzahl k-cups/caps/gons
         Positive Fraction ES Theorem
15. Vorlesung, Do. 7.6.2018 
         Beweis Positive Fraction ES Theorem  
         Beweis Suk's Theorem
      Weitere Ergebnisse
         Gitter-ähnliche Punktmengen haben (n^1/3)-gons
         Polynomieller Zählalgorithmus
         g(5)=9, g(6)=17
16. Vorlesung, Mi. 13.6.2018 
      Computerunterstützter Beweis für g(6)=17
         Grassmann-Plücker Relationen und Chirotop Axiome
         Realisierbarkeitsproblem
   Erdős Problem auf leeren konvexen Polygonen
      Quadratische untere Schranke für h_3(n)
      Harborth's Theorem
         Beweis h(5)<=20
17. Vorlesung, Do. 14.6.2018 
      Horton Sets
      Leere Sechsecke
      Quadratische obere Schranke für h_3(n)
18. Vorlesung, Mi. 20.6.2018 
   Voronoi Diagramm und Delaunay Triangulierung
      Voronoi-Zellen und das Diagramm
      Delaunay Triangulierung als Dual des VD
      Leere Kreise als Zeugen für Flächen und Kanten des DT
      DT als untere konvexe Hülle des Paraboloid-Liftings
19. Vorlesung, Do. 21.6.2018 
      Lawson Flips
      Flip Algorithmus und seine Komplexität
   Randomisiert inkrementelle Berechnung der DT    
      Die Verzweigungsstruktur (Historiengraph)
      Größe der Verzweigungsstruktur
20. Vorlesung, Mi. 27.6.2018 
      Aufwand für die Lokalisierung neuer Punkte
   Sekundärpolytope
      Reguläre Triangulierungen
      Sekundärpolytop als konvexe Hülle von Volumensvektoren
21. Vorlesung, Do. 28.6.2018 
     Reguläre Triangulierungen als Ecken des Sekundärpolytops
     Das Assoziaeder
  Gitterpunktenumeration
     Satz von Pick
22. Vorlesung, Mi. 4.7.2018 
     Beweis des Satzes
     Satz von Ehrhart in 2 Dimensionen
        Beispiel: Einheitsquadrat
        Beispiel: Dreieck
     Die Sätze von Ehrhart
23. Vorlesung, Do. 5.7.2018 
        Diskretes Volumen
	Kegel
	Zerlegung in simpliziale Kegel
	Gitterpunktfunktionen
24. Vorlesung, Mi. 11.7.2018 
        Das fundamentale Parallelepiped
	Polynomialreihen als rationale Funktionen
	Reziprozität für Kegel
25. Vorlesung, Do. 12.7.2018 
      Das Ordnungspolytop
        Triangulierung durch lineare Erweiterungen
	Volumen
	Klassifikation der Ecken
      Das Kettenpolytop
 	Klassifikation der Ecken
	Satz von Stanley
26. Vorlesung, Mi. 18.7.2018 
     Arrangements von Hyperebenen
        Anzahl der Zellen
     Arrangements von Pseudogeraden
        Isomorphie
	Projektive und Euklidische Arrangements
	Es gibt immer 3 gewöhnliche Punkte
	Streckbarkeit
27. Vorlesung, Do. 19.7.2018 
        Milnor-Thom Theorem und
	   Anzahl Geradenarrangements (obere)
        Anzahl Pseudogeradenarr. (untere)
        Anzahl Pseudogeradenarr. (obere)
           via Fingerabrduck
	Satz von Levi (Dreiecke)
Back to main page.