Inhaltsverzeichnis

Konstruktive Kombinatorik

Wintersemester 2012/13
Stefan Felsner

1. Vorlesung, Mo. 15.10.2012

  Modelle für die Teilmengen von [n]
  Zählen und Erzeugen der Teilmengen von [n] 
  Binomialkoeffizienten
     Binomialformeln und kombinatorische Beweise

  Erzeugen von n-Tupeln
     Binäre n-Tupel und binäres Zählen
     Verallgemeinerte Erzeugung durch Zählen
     Der standard Gray Code
     Berechnung von g(k) aus k und umgekehrt

   Gray-Codes abstrakter
     Hamiltonkreise im Hyperwürfel
     Spezielle Bedingungen: Balanced, long runs, complemented
     Konstruktion monotoner Gray-Codes

   Middle Levels Problem
     Lange Kreise zwischen benachbarten Rängen in Bn
     α-Sequenzen und monotone Gray-Codes
   Erzeugen von k-Mengen
     Lex- und CoLex-Ordnung
     Eine Zahlendarstellung  

    Schatten und das Kruskal-Katona Theorem
  Revolving Door Konstruktion
  Strong Revolving Door Konstruktion
  Paritätsbedingungen für einen adjacent interchange Gray Code

  Permutationen
    Notationen und Modelle
    Lexikographische Ordnung
    Inversionen und Inversionsfolgen
    Das Rang-Problem für die Lex-Ordnung und eine Zahlendarstellung

    Die erzeugende Funktion für Inversionen
    Permutaeder als konvexe Hülle
      Ungleichungen ür das Permutaeder
      Das Permutaeder als Minkowski-Summe von Strecken  

    Inversionsmengen von Permutationen   
      Die schwache Bruhat Ordnung
    Präsentation von Gruppen mit Erzeugenden und Relationen
      Die Sn als Coxetergruppe
      Reduzierte Darstellungen und Pseudogeradenarrangements

  Plaine Changes - ein Gray-Code für Permutationen
  Permutationen und Zyklen
    Standardzyklendarstellung
    Stirling Zahlen erster Art 

    Eine Polynomidentität für Stirling Zahlen
  Zykel von Permutationen und "Names in Boxes"
Partielle Ordnungen (posets) und lineare Erweiterungen
  Der Graph G(P) der linearen Erweiterungen von P 

  Distanz und Durchmesser in Graphen
  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)
  Kleitmans Lemma 
  Ideale, Filter und Antiketten

Kleitmans Lemma, Anwendungen und verwandte Themen
  Der Beweis von Kleitmans Lemma
  Anw. Eine einfache Korrelationsungleichung
  Anw. Intersecting Families
  Ahlswede-Daykin, four-Function Theorem  

  Kleitmans aus AD
   Distributive Mengenfamilien und Verbände
  AD Theorem für distributive Verbände
  Anw. Percolation
  Korrelation von Ordnungseigenschaften

 Der Satz von Graham-Yao-Yao für Ordnungen der Weite 2
   Lineare Erweiterungen als Gitterpfade
   Der distributive Verband der linearen Erweiterungen
 Die FKG Ungleichung
   Anw. Eine Ungleichung für monotone Vektoren

   Zählen von linearen Erweiterungen
     Serielle und parallele Komposition
      Eine Hook-Formel für Bäume
        Ein probabilistischer Beweis
        Bemerkungen zur Hook-Formel für Ferrers Ordnungen  
     Catalan Ordnungen und die Catalan Zahlen  

        Spiegelungsprinzip
        Zählen mit Äquivalenzklassen
     Fibonacci Ordnungen
        Fibonacci Zahlen
        Rekursionen
 

        Die Rekursionsmatrix
     Schranken für die Anzahl der linearen Erweiterungen
        Untere Schranke [Satz von Sidorenko]
          Pfade und Flüsse in einem Netzwerk
        Obere Schranke
          Antikettenpolytop

  Turniere
     Satz vom König
     Existenz von Hamiltonpfaden
     Dicuts und Hamiltonkreise
     Score Folgen und der Satz von Landau
     Majorization 

     3-Rotationen verbinden Turniere mit derselben Score Folge
     Maximale Anzahl von Hamiltonpfaden in einem n-Turrnier
        Satz von Szele
        Satz von Alon
     Die Permanente einer Matrix
        Vermutungen von Minc und van der Waerden

  Tilings
    Domino Tilings 
      Rechtecke und Rechtecke mit Löchern
      Allgemeine Gebiete
    Pflasterungen mit Vs (L-Trominos)
    Nichtexistenzkriterien
      1. Flächenkriterium
      2. Färbungskriterien

           Tilings mit Ts, Stäben und Ls
      3. Homologiekriterium
           Die abelsche freie Gruppe und die Kacheluntergruppe
           Beispiele mit Dominos und Ls

        Aztekische Diamanten und Z-Kachelungen
          Homologie tut es nicht.
          Ein Färbungsargument fuer n = 1,2 mod 2
      4. Homotopiekriterium
          Die frei Gruppe und die Randwortuntergruppe
          Anwendungsbeispiele
            Windungszahlen 

   Zählen von Tilings
     Dominotilings des Aztekischen Diamanten
       Domino Shuffling

     Dominotilings des Aztekischen Diamanten
       Überlagerung von Matchings
     Fries-Muster 

      Fries-Muster und Überlagerung von Matchings
      Fries-Muster und Dogsons Determinantenregel 
  Zählen von Matchings und Determinanten
    Die Permanente

    
    Kasteleyn Signaturen
      Beispiele - nicht jeder bipartite Graph hat eine KS
      Bipartite planare Graphen besitzen eine KS

    Die Kasteleyn Formel für die Anzahl der DTs einex nxm Bretts  Rhombische Parkettierungen im Dreiecksgitter
    Partitionen und Plane Partitions
    Die MacMahon Formel und ihre gewichtete Variante
    Deweis der Rekursion mittels Überlagerung    

 Rhombische Tilings des 2n-Gons
   Zonen und ihr Kreuzungsverhalten
   Äquivalens mit Pseudogeradenarrangements
   Dreiecksflips
   Je zwei Arrangements sind über Dreiecksflips verbunden 
  

   Obere und untere Schranken für die Anzahl der Arrangements
      Fingerasbdrücke
      Eine untere Schranken Konstruktion
      Obere Schranke für Geradenarrangements
   Bessere Schranken
      (Vortragsfolien EPFL Aug. 2010)