Table of Content

Ordnungstheorie

Sommersemester 2010
Stefan Felsner

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

1. Vorlesung, Mo. 12.4.2010 

  Grundlagen
     Begriffe und Definitionen
     Graphen und Ordnungen, das Diagramm
     Beispiele von Ordnungen
        Inklusionsordnungen
        Ordnungen aus Ordnungen 
           (Down-sets / Erweiterungen)
2. Vorlesung, Di. 13.4.2010 
        Kombinatorische Ordnungen
           (Dyck-paths / Rotationen auf Bäumen / weak Bruhat)
     Ketten und Antiketten
        Bijektionen: Antiketten <-> Ideale
        Satz von Dilworth
           Antikettenzerlegungen und Perfect-Graph-Theorem
           Induktionsbeweis (Perles)
3. Vorlesung, Mo. 19.4.2010 
           Dilworth via bipartites Matching
        Der Verband der maximum Antiketten
           Ordnungsautomorphismen
           Satz von Sperner
     Lineare Erweiterungen und Dimension
        Der generische Alg. für lineare Erweiterungen
        Realizer und Dimension
4. Vorlesung, Di. 20.4.2010 
        Dimension und Einbettung in Rk
        Standardbeispiele und Dimension Boolscher Verbände
        Dimension und Weite
        Komplexität und Codierung
     2-dimensionale Ordnungen
        Konjugierte Ordnung
        Non-separating linear extensions
5. Vorlesung, Mi. 26.4.2010 
        Interval Containment Graphs
        Permutationsgraphen
        Algorithmen für Ketten- 
           und Antikettenzerlegung
           in O(n log n)
     Transitive Orientierung
        Γ und Γ* Relation
        Implikationsklassen
6. Vorlesung, Di. 27.4.2010 
     Modulare Dekomposition
        Starke Module und Dekompositionsbaum
        Der Dekompositionssatz
        Dekomposition und transitive Orientierung
7. Vorlesung, Mo. 3.5.2010 
     Algorithmen für transitive Orientierung
        Partitionsverfeinerung (ordered vertex partitioning)
        Colexikographische Breitensuche 
        Anwendung auf prime Vergleichbarkeitsgraphen
8. Vorlesung, Di. 4.5.2010 
        Die Algorithmen für allgemeine Vergleichbarkeitsgraphen
        Laufzeiten: Orientierung vs. Erkennung
     Dimension von Ordnungen
        Dimension und Module -- Vergleichbarkeitsinvarianz
        Die Ungleichung von Hiraguchi
        Kritische Paare
9. Vorlesung, Mo. 10.5.2010 
        Alternierende Zykel und Realizer
        Hypergraphen färben und Dimension
        3-irreduzible Ordnungen
10. Vorlesung, Di. 11.5.2010 
        Der Graph im Hypergraphen
        Ein Beispiel mit großer Dim. und kleinem χ
        Splits 
        Eine Schranke für die Dim von Splits
     Intervallordnungen
11. Vorlesung, Mo. 17.5.2010 
        Charakterisierungen von Intervallordnungen
        Charakterisierungen von Semiordnungen
        Dimension von Semiordnungen
12. Vorlesung, Di. 18.5.2010 
        Dimension von Intervallordnungen
           Markierungen und lineare Erweiterungen
           Binäres Markieren
           Logarithmische Schranken in Höhe und Weite
13. Vorlesung, Mo. 31.5.2010 
          Shift-Graphen und eine untere Schranke
             Kantenfärbungszahl gerichteter Graphen
             Kantenfärbungszahl vs. Chromatische Zahl
             Gerichtete Line-Graphen
             Färbungszahl von Shift-Graphen
14. Vorlesung, Di. 1.6.2010 
        Intervalldimension
           Boxdarstellung
           Die Ordnung der extremen Ecken einer Boxdarstellung
           Kanonisieren der Boxdarstellung
           Intervalldimension von P und Dimension von B(P)
15. Vorlesung, Mo. 7.6.2010 
        Greene-Kleitman Theorie
             Dualitätssatz für l-Antiketten
             Dualitätssatz für k-Ketten
             t-Phaenomene
             konjugierte Partitionen
           Der Network-Flow Beweis von Frank
16. Vorlesung, Di. 8.6.2010 
          Dualitätssatz für l-Antiketten und t-Phaenomen 
          mit Beweis von Perfect und Saks
17. Vorlesung, Mo. 21.6.2010 
          Young-Tableaux
          Robinson-Shensted-Knuth Korrespondenz
          Skelette von 2-D Ordnungen
          Viennots Beweis
          k-Ketten und Skelette
18. Vorlesung, Di. 22.6.2010 
       Zählen von linearen Erweiterungen
          Down-set Verband und dynamisches Programmieren
          #P-Vollständigkeit und FPRAS
          Beispiele: Binomialkoeffizienten, Catalan, Fibonacci
          Hook-Formeln für Bäume und Ferrers Posets
          Ein probabilistischer Beweis für die Hook-Formeln für Bäume
19. Vorlesung, Mo. 28.6.2010 
          Eine Rekursion für lineare Erweiterungen
       Polytope zu Ordnungen
          Das Ordnungspolytop und lineare Erweiterungen
          Das Volumen des Ordnungspolytops
          Die Ecken (Ideale)
20. Vorlesung, Di. 29.6.2010 
          Das Kettenpolytop
          Der Satz von Stanley zum Volumen des Kettenpolytops
          Eine Ungleichung zur Anzahl lin. Erw, von 2-dim Ordnungen 
          Eine Ungleichung zur Anzahl lin. Erw, von LYM Ordnungen
21. Vorlesung, Mo. 12.7.2010 
       Balancierende Paare
          Allgemeines Sortieren und die 1/3-2/3 Vermutung
          Zum Stand der Dinge
          Der Kahn-Linial Beweis für die Existenz balancierender Paare
              Brunn-Minkowski
22. Vorlesung, Di. 13.7..2010 
      On-line Probleme für Ordnungen
         On-line Spiele und Färbungen
         On-line Antikettenzerlegungen
            Untere Schranke
         On-line Kettenzerlegungen
            First Fit
            up-growing on-line Ordnungen

Back to main page.