Table of Content

Graphen und Geometrie (Diskrete Strukturen III)

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, Di. 17.4.2018 

  Kreuzungen
     Kreuzungszahl
     Topologischer Graph / Geometrischer Graph
     Vermutungen zur Kreuzungszahl von Km,n und Kn
        (ein Artikel zur Geschichte: Beineke Wilson 2010)
     Die Moon Konstruktion
2. Vorlesung, Fr. 20.4.2018 
     Kreuzungszahlkonstante für Kn existiert
     Zarankiewicz ist "stärker"
  Thrackles
     Die Thrackle Vermutung
     Thrackles haben lineare Kantenzahl
        Kreuzungslemma für Kreise
        Bipartite Subgraphen
        Für bipartite Graphen gilt: generalized Thrackle ⇔ planar
3. Vorlesung, Di. 24.4.2018 
       Generalized Thrackles haben höchstens 4n Kanten
     Satz von Hanani-Tutte - ein geometrischer Beweis
  Das Crossing Lemma
     Der probabilistische Beweis
     Zur Konstanten im Crossing Lemma
4. Vorlesung, Fr. 27.4.2018 
    Kantenzahl 1-planarer Graphen
    Kantenzahl 2-planarer Graphen
    Anwendungen des Crossing Lemma
      Inzidenzen (Szemeredi Trotter)
5. Vorlesung, Fr. 4.5.2018 
        Der Elekes Beweis für max(Σ,Π) > n^5/4
        Einheitsabstände
  Turan Probleme für geometrische Graphen
     Konvexe geometrische Graphen ohne k+1 parallele Kanten
6. Vorlesung, Di. 8.5.2018 
     Geometrische Graphen ohne parallele Kanten	
     Geometrische Graphen ohne k+1 disjunkte Kanten
7. Vorlesung, Fr. 11.5.2018 
      Konvexe geometrische Graphen ohne k+1 paarweise kreuzende Kanten
         irrelevante, randständige und relevante Kanten 
         Sterne und ihre Bisektoren
         Bemerkungen zu Flips und der Anzahl von k-Triangulierungen
8. Vorlesung, Di. 15.5.2018 
     Kantenzahl von k-quasiplanaren Graphen
        Stand der Forschung
        Ein Entladungsargument für 3-quasiplanare Graphen
  Orientierungen (planarer) Graphen mit Anwendungen
     Ordnungen - Verbände - Dimension [Folien]
9. Vorlesung, Fr. 18.5.2018 
     Dimension von Ordnungen
     Dimension und Planarität
     Dimension und Komplexität
     Satz von Schnyder und verwandte Resultate
  α-Orientierungen und Verbände
     α-Orientierungen
     Beispiele: aufspannende Bäume, Matchings
     [Folien]
10. Vorlesung, Di. 22.5.2018 
    Schnyder Woods 
    α-Orientierungen induzieren distributive Verbände 
    c-Orientierungen und Δ-Bonds
  Δ-Bonds und ULD Verbände 
    U-Färbungen und ULD Verbände 
    [Folien]
11. Vorlesung, Fr. 25.5.2018 
  Distributive Verbände und Markov Ketten
    Markov Ketten, kleine Einführung
    Eine Markov Kette für distributive Verbände
    Coupling from the past
    2-Orientierungen planarer Quadrangulierungen
    Zwei Resutlate zur Mischrate der Markov Kette auf 2-Orientierungen
    [Folien]
 Graphen und Rechteckszerlegungen
    Eine Rechteckszerlegung und 5 Graphen
    Zwei Konstruktionen von Rechteckszerlegungen aus Graphen
    [Folien]
12. Vorlesung, Di. 29.5.2018 
  Quadratdarstellungen
       Squarings aus elektrischen Flüssen (die BSST Methode)
       Squarings aus Gleichungssystemen
       Quadratkontaktdarstellungen (Schramm und Lovasz)
       Quadratkontaktdarstellungen aus Gleichungssystemen
      [Folien]
13. Vorlesung, Fr. 1.6.2018 
  Einleitung: Kartogramme
    Flächenuniversalität
       flächenuniverselle Graphen: stacked triangulations, Subgraphen
       nicht flächenuniverselle Graphen: Oktaedergraph (3 Beweise), Eulersche Triangulierungen
       Charakterisierung realisierbarer Flächenzuweisungen (Abgeschlossenheit)
14. Vorlesung, Di. 5.6.2018 
   realisierende Zeichnungen mit Knicken
      T-Kontaktdarstellungen
      schwach äquivalente realisierende Rechteckszerlegungen
15. Vorlesung, Fr. 8.6.2018 
    Flächenuniversalität von Triangulierungen
       Charakterisierungen
       hinreichende Kriterien
16. Vorlesung, Di. 12.6.2018 
  Homothetische Dreieckskontaktdarstellungen
     induzierter Schnyder Wood
     Gleichungssystem
         eindeutig loesbar
      Wechselkanten in Loesung mit negativen Variablen
         Definition
17. Vorlesung, Fr. 15.6.2018 
        bilden Vereinigung von gerichteten Kreisen
     Konstruktion der Kontaktdarstellung aus nichtnegativer Loesung
     Flip im Schnyder Wood ändert Vorzeichen der umschlossenen Variablen
18. Vorlesung, Di. 19.6.2018 
  Geometrische Durchschnittsgraphen (Χ-boundedness)
     Komplexität von Durchschnittsdarstellungen
     χ-Beschränktheit von Quadraten
     χ-Beschränktheit von Rechtecken
19. Vorlesung, Fr. 22.6.2018 
     χ-Beschränktheit von Pseudokreisscheibenfamilien 
         Die union complexity von Pseudokreisscheibenfamilien 
     Dreiecksfreie Segmentgraphen mit grosser chromatischer Zahl
         (Eine geometrische Version der Burling Konstruktion)
20. Vorlesung, Di. 26.6.2018 
     χ-Beschränktheit von Overlap-Graphs
          BFS-Reduktion 
          m-gute Darstellungen
21. Vorlesung, Fr. 29.6.2018 
     k-Mengen und k-Kanten
         Alternierungs-Lemma + Lovasz Lemma
         Die klassische Schranke
         Die Welzl Identität
22. Vorlesung, Di. 3.7.2018 
            Punkte in konvexer Lage
            Verschieben -- Mutationen
         Anzahl ≤k-Mengen
23. Vorlesung, Fr. 6.7.2018 
      Schranken für k-Mengen in allen Dimensionen (Übersicht)
      k-Facetten
         h- und s-Vektor
	 Lovasz Lemma für k-Facetten
	 Eine obere Schranke für k-Mengen in 3-d
24. Vorlesung, Di. 10.7.2018 
      Gradlinige Kreuzungszahl des K
         Kreuzungszahl und k-Kanten
         Kreuzungszahl und ≤k-Kanten
	 Eine untere Schranke an ≤k-Kanten
	     k-Kanten in dualen Pseudogeradenarrangements
25. Vorlesung, Fr. 13.7.2018 
            Minimierende Beispiele haben nur 3 extremale Pseudogeraden
            Eine Rekursion
26. Vorlesung, Di. 17.7.2018 
            Grüne Streifen Lemma
         Konstruktionen für obere Schranken
     Federeinbettungen
         Energiefunktion
27. Vorlesung, Fr. 20.7.2018 
         Konvexität der Energiefunktion
	 Berechnen von Federeinbettungen
	   Iteration
	   Lineares System der Gleichgewichtsbedingungen
	      diskrete harmonische Funktionen
	      Eindeutigkeit der Lösung
	 Satz von Tutte
Back to main page.