Table of Contents

Combinatorics

Sommer Term 2009
Stefan Felsner

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

1. lecture, 20.4.2009 

   What is Combinatorics
     What does it mean to count?
       Aspects of counting derangements (fixed point free permutations)
       P.R.de Montmort
       sequence A000166 in OEIS
       recurrence - summation - asymptotics - generating function
2. lecture, 20.4.2009 
     Orthogonal Latin Squares 
       (Euler's 36 officers problem)
       Orthogonal Latin squares from groups
       There are at most N-1 MOLS of order N
       MOLS and projective planes
       Projective planes and fields
3. lecture, 27.4.2009 
   Basic Counting
      Basic rules for counting
      Binomial coefficients
        Models and identities
        Extending binomial coefficients 
        (positive integer -> integer -> complex -> polynomial)
4. lecture, 27.4.2009 
      The binomial theorem
      The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind
5. lecture, 4.5.2009 
      Partitions on an integer
        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous
        Euler's Pentagonal Number Theorem
6. lecture, 4.5.2009 
      Formal power series
        Basic operations
        Bernoulli numbers and sums
        Composition of FPS
        Catalan numbers and their generating function
7. lecture, 11.5.2009 
      Solving linear recurrences
        The general approach
        Fibonacci numbers
        Spanning trees of Gn
8. lecture, 11.5.2009 
      q-Enumeration
        Permutations and inversions
        01-words and inversions
        A q-binomial theorem
        Subspaces of q-vectorspaces
        Another q-binomial theorem
9. lecture, 18.5.2009 
   Finite sets and posets
        Intersecting families of subsets
        Posets
        Lattices
        Substructures in posets and lattices
10. lecture, 18.5.2009 
        Sperner's Theorem
           LYM inequality
        Erdös-Ko-Rado Theorem
           cyclic permutations
        Small maximal intersecting families of k-sets
11. lecture, 25.5.2009 
        Shadows
          Sperner's Theorem again
          Kruskal-Katona Theorem
        Posets; products and ranks
        Symmetric chains
12. lecture, 25.5.2009 
          Symmetric chain decompositions for multisets
          Symmetric chain decomp. and pairing brackets
          An application to Dedekind's problem
      Duality theorems
        Dilworth's Theorem
13. lecture, 8.6.2009 
        König-Egervary matching theorem
        The Marriage Theorem (Hall condition)
        A quantified Marriage Theorem
        On the number of Latin squares
14. lecture, 8.6.2009 
      The matching polytope of a bipartite graph 
        LP relaxation for max matching
        polyhedra, polytopes and their vertices
        The TDI property of the incidence matrix
        LP-duality and the König-Egervary theorem
15. lecture, 15.6.2009 
      Two definitions for lattices
        Distributive lattices
        Down-sets and antichains
        Fundamental Theorem of Finite Distr. Lattices
16. lecture, 15.6.2009 
      Linear extensions
        generic algorithm
        dimension of posets
          Boolean lattices and standard examples
        bounds for dimension
17. lecture, 22.6.2009 
        More bounds for dimension
          dimension of incidence posets of graphs
          dimension of complete graphs
18. lecture, 22.6.2009 
       The order poytope O(P)
         vertices and volume of O(P)
         the chain polytope C(P)
         vertices and volume of C(P)
         antiblocker and linear extensions of 2-dimensional posets
19. lecture, 29.6.2009 
       Chromatic number 
         Colorings, independent sets, cliques
         b-colorings
         The b-chromatic number of odd cycles
         b-cliques
         IP formulations for χ and ω
         Fractional chromatic number
20. lecture, 29.6.2009 
         Colorings and homomorphisms
         Kneser graphs
         Fractional chromatic number of Kneser graphs
         Chromatic number of Kneser graphs
         A bound for the integrality gap of coloring
21. lecture, 6.7.2009 
       Möbius inversion
         Incidence algebra of a poset
         Zeta function and  Möbius function
         Möbius function of chains and products
         Applications
22. lecture, 6.7.2009 
       Involutions
         Vandermonde determinant and tournaments
         Lemma of Lindström, Gessel-Viennot
23. lecture, 13.7.2009 
       Catalan numbers
         Ten Catalan families
            some bijections
         Determining the numbers
            cycle lemma
24. lecture, 13.7.2009 
            path reflection
            Narayana numbers via LGV Lemma 
         Further directions
            two lattices on Catalan families
            rotations and flips
            the associahedron

Back to the course page.