Table of Content

Ordnungstheorie

Sommersemester 2016
Stefan Felsner & Veit Wiechert

1. Vorlesung, Mo. 18.4.2016

  Grundlagen
     Begriffe und Definitionen
  Graphen aus Ordnungen
  Das Diagramm
  Klassen von Ordnungen
        Inklusionsordnungen
        Verbände
        Kombinatorische Ordnungen
           (Permutationen, Gitterpfade, Bäume mit Rotationen)

  Ordnungen aus Ordnungen 
     Down-sets (Idealverband)
     Erweiterungen
  Zählen von Ordnungen
     Kleitman-Rothschild
  Ordnungen aus zeitlichen Bedingungen
     Lawlers Greedy-Alg für 1|prec|fmax
     Antimatroide

  Satz von Dilworth
      Induktionsbeweis (Perles)  
      Dilworth via bipartites Matching
      Antikettenzerlegungen und Perfect-Graph-Theorem
  Beyond Dilworth
      Der Satz von Gallai Milgram
      Gewichteter Dilworth

      Die Sätze von Greene und Kleitman
         RSK Korrespondenz (Bijektion zwischen Permutationen 
              und Paaren von Young Tableaux derselben Gestalt)
  Verbände
     Ordnungstheoretische und algebraische Definition
     Dedekind MacNeille Vervollständigung

        DM(P) ist ein Verband
        DM(P) ist kleinster Verband in den P eingebettet werden kann
     Distributive Verbände
        Der Hauptsatz über endliche distributive Verbände (Birkhoff)

            Zweiter Teil des Beweises (FTFDL - Birkhoff)
         Antikettenverbände
            Downset-Verband
            Verband der maximum Antiketten
            Ordnungsautomorphismen und Satz von Sperner
  Lineare Erweiterungen und Dimension
     Existenz linearer Erweiterungen
        generischer Algorithmus
     Realizer und Dimension

     Dimension und Einbettung in Rk
     Standardbeispiele und Dimension Boolescher Verbände
        Dimension und Weite
     2-dimensionale Ordnungen
        Konjugierte Ordnung
        Non-separating linear extensions

        Inklusionsordnung von Intervallen
     Hiraguchi-Ungleichung
     Kritische Paare und alternierende Zykel
     Kompatible Mengen
     Dimension als Färbungsproblem

     Dimension von planaren Ordnungen
         Baker, Fishburn, Roberts (planare Ordnungen mit 0 und 1)
         Moore, Trotter (planare Ordnungen mit 0)
         planare Verbände und Charakterisierungen von 2-dimensionalen Ordnungen
         Kelly Beispiele
         Obere Schranken

   Erkennung von Vergleichbarkeitsgraphen
      Vergleichbarkeitstestgraph
      G ist Vergl.Graph gdw. G konsistent

      Laufzeit für Test ob Graph ein Vergleichbarkeitsgraph ist
      Autonome Mengen
      Dimension ist Vergleichbarkeitsinvariante
   Intervallordnungen
      Charakterisierungssatz

      Charakterisierungen von Intervallordnungen
      Charakterisierungen von Semiordnungen
      Dimension von Semiordnungen
      Dimension von Intervallordnungen
         Markierungen und lineare Erweiterungen
 

         Binäres Markieren
         Logarithmische Schranken in Höhe und Weite
         Doppeltlogarithmische Schranke (FHRT'91)

         Fäbungszahl des Shift-Graphen G(n,3) als untere Schranke
   Dimension von Graphen
      Inzidenzordnungen
      Nicht-planare haben dim > 3
      Kritische Paare
         Dimension von Graphen mit Permutationen der Knoten	 

     Dimension von Kn
        HM-Antiketten
        Der Beweis von Hosten-Morris

     Dimension planarer Graphen
        Satz von Schnyder
           Beweis unter Verwendung von Zeichnungen
           Beweis direkt mit Schnyder Woods 
        Sätze von Brightwell und Trotter
           Dimension von Seitenverbänden, untere Schranke
           Schnyder Woods von 3-zush planaren Graphen

           Orthogonale Flächen
        Dimension von PVF für planar maps
	   Der Winkelgraph als Subgraph einer Quadrangulierung
           Bipartite Ordnungen t-separabler Familien

           Segment-Kontakt-Darstellungen von Quadrangulierungen
              Separating decompositions  
                 Existenz, Bäume, Äquatorlinie
	      Alternierende Bäume 
              Bijektion: alternierende Bäume <-> binäre Bäume
           Der Split einer Ordnung     
           Kanten in Segment-Kontakt-Darstellungen einbauen
              Liefert Realizer von split(PVEF)

    Ordnungspolytop
    Kettenpolytop
    Satz von Stanley

    Konvexe Ecken und  Antiblocker
    Antikettenpolytop
    Balancierte Paare
        Sortieren mit Vergleichen
        1/3-2/3 Vermutung

    Kahn-Linial: Jede Ordnung ist (1/2e)-balanciert
    Weite-2 Ordnungen sind 1/3-balanciert

   Zur Anzahl linearer Erweiterungen
       Komplexität (#P vollständig)
       FPRAS existiert
          Markov Kette für lineare Erweiterungen
       Serielle und parallele Komposition 
       Hook Formel für Bäume
          Ein Beweis über einen Zufallsprozess
       Hook Formel für Ferrers Posets

       Catalan Zahlen als e(P)
       Fibonacci Zahlen als e(P)
       Satz von Siderenko
          e(P) \geq sum( e(P-x) : x\in A )
       Ein Satz für 3 Ordnungen
       2-dimensionale: e(P)e(Pkonj) \geq n!
       Obere Schranke: e(P) \leq \Prod 1/b_x

       Optimale Punkte für die obere Schranke
       Ungleichungen fÜr optimale Punkte
    Korrelation
       AD-Ungleichung
       Kleitmans Lemma
       Korreletion für lineare Erweiterungen (Graham, Yao, Yao)

  Der Graph G(P) der linearen Erweiterungen von P 
     Der Lineare Erweiterungs Durchmesser led(P)
     led(P) und Zeichnen von Ordnungen
  Der Lineare Erweiterungs Durchmesser von Boolschen Verbänden
     Die revlex Ordnung  
     Die Klassen CD,I
     Der Beitrag der Klassen zu led(Bn)
        eine Anwendung von Kleitmans Lemma