Table of Contents

Combinatorics

Sommer Term 2011
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, 11.4.2011 

   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, 11.4.2011 
     Orthogonal Latin Squares 
       (Euler's 36 officers problem)
       Orthogonal Latin squares from groups
       MOLS (mutually orthogonal Latin squares)
       There are at most N-1 MOLS of order N
       MOLS and projective planes
3. lecture, 18.4.2011 
   Basic Counting
      Basic rules for counting
      Binomial coefficients
        Models and identities
        Extending binomial coefficients 
        (positive integer -> integer -> complex -> polynomial)
      The binomial theorem
   Fibonacci numbers
      Basic models
4. lecture, 18.4.2011 
      Identities
      Number system (Zeckendorf)
      Binet's formula via generating function
                      via linear algebra
      Continued fractions and continuants
5. lecture, 2.5.2011 
      The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind
      Partitions on an integer
        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous
6. lecture, 2.5.2011 
        Euler's Pentagonal Number Theorem 
      Formal power series
        Basic operations
        Bernoulli numbers and sums
7. lecture, 9.5.2011 
        Composition of FPS
        Catalan numbers and their generating function 
      Solving linear recurrences
        The general approach
8. lecture, 9.5.2011 
        Spanning trees of Gn
        Exponential generation function for Fibonacci numbers
      q-Enumeration
        Permutations and inversions
        Mac Mahon's maj-index and the equidistribution theorem
9. lecture, 16.5.2011 
        01-words and inversions
        A q-binomial theorem
        Subspaces of q-vectorspaces
        A second q-binomial theorem
10. lecture, 16.5.2011 
   Finite sets and posets
        Intersecting families of subsets
        Posets and lattices
        Substructures in posets and lattices
        Sperner's Theorem - LYM inequality
        Erdös-Ko-Rado Theorem - cyclic permutations
        Small maximal k-intersecting families
11. lecture, 23.5.2011 
        Shadows
          Sperner's Theorem again
          Kruskal-Katona Theorem
12. lecture, 23.5.2011 
        Symmetric chains
          Symmetric chain decompositions for multisets
          Symmetric chain decomp. and pairing brackets
          An application to Dedekind's problem
13. lecture, 30.5.2011 
 
      Duality theorems
        Dilworth's Theorem       
        König-Egervary matching theorem
        The Marriage Theorem (Hall condition)
        A quantified Marriage Theorem
        On the number of Latin squares
14. lecture, 30.5.2011 
 
      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, 6.6.2011 
    Polya Theorie: Counting with symmetries
      Necklaces and colored cubes - two introductory examples
      Permutation groups and the cycle index
      The Lemma of Cauchy-Frobenius-Burnside
16. lecture, 6.6.2011 
      Polya's first theorem: counting orbits of RD
      Weights on R and the induced weight on RD
      Polya's fundamental theorem:
17. lecture, 20.6.2011 
      Linear extensions
        generic algorithm
        dimension of posets
          Boolean lattices and standard examples
        bounds for dimension 
        characterizations of 2-dimensional posets
18. lecture, 20.6.2011 
     Algorithms for chain- and antichain partitions
       the 2-dimensional case
       Young-Tableaux and the Robinson-Shensted correspondence
          bumping
          Viennot's proof via skeletons 
       Connections to the Greene-Kleitman theory
19. lecture, 27.6.2011 
   Design Theory
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
     Kirkman's problem
20. lecture, 27.6.2011 
     Resolvable designs
     Solutions to Kirkman's problem
     Projective planes as designs
     A construction of the plane S(2,5,21) from K6
     Fisher's inequality
21. lecture, 4.7.2011 
       Möbius inversion
         Incidence algebra of a poset
         Zeta function and  Möbius function
         Möbius function of chains and products
         Applications
22. lecture, 4.7.2011 
       Involutions
         Vandermonde determinant and tournaments
         Lemma of Lindström, Gessel-Viennot
23. lecture, 11.7.2011 
       Catalan numbers
         Ten Catalan families
            some bijections
         Determining the numbers
            path reflection
24. lecture, 11.7.2011 
            cycle lemma
            Narayana numbers via LGV Lemma 
         Further directions
            two lattices on Catalan families
            rotations and flips
            the associahedron

Back to the course page.