Combinatorics

Sommer Term 2021 Stefan Felsner

Content of individual lectures: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 25 , 26 , 27 ,

1. lecture, 13.04.2021

What is Combinatorics - introductory examples
Derangements
Aspects of counting derangements (fixed point free permutations) P.R.de Montmort
sequence A000166 in OEIS
recurrence - summation - asymptotics - generating function
2. lecture, 15.04.2021
Orthogonal Latin Squares
(Euler's 36 officers problem)
Orthogonal Latin squares of odd order from groups
MOLS (mutually orthogonal Latin squares)
There are at most n-1 MOLS of order n
Projective planes
3. lecture, 20.04.2021
Basic Counting
Basic rules for counting
Binomial coefficients
Models and identities
Extending binomial coefficients
Extending binomial identities to polynomial identities
The binomial theorem
Combinatorics of Permutations
The type of a permutation
Enumeration of permutations of given type
4. lecture, 22.04.2021
The quality of the recording is terrible - I didn't pin speakers view - sorry.
Here are my notes for the lecture [Lecture-4-notes.pdf]
Permutations with k cycles
Stirling numbers of first kind
Recursion and raising factorials
Expected number of cycles
The twelvefold way
Partitions of a set
Stirling numbers of second kind
5. lecture, 27.04.2021
Stirling numbers of 2nd kind
Stirling inversion
Partitions of an integer
Generating function of partitions
Distinct and odd are equinumerous
6. lecture, 29.04.2021
Euler's Pentagonal Number Theorem
Fibonacci numbers
Identities
7. lecture, 04.05.2021
Fibonacci numbers
Binet's formula via generating function
via linear algebra
Solving linear recurrences
The general approach (partial fraction decomposition)
Exponential generating functions (differential equations)
8. lecture, 06.05.2021
Formal power series
Basic operations
Bernoulli numbers and a summation formula
Composition of FPS
The symbolic method
Catalan numbers and their generating function
9. lecture, 11.05.2021
q-Enumeration
Permutations and inversions
Mac Mahon's maj-index and the equidistribution theorem
Eulerian numbers
Equidistribution of des and exc
10. lecture, 18.05.2021

Eulerian numbers
Worpitzky's identity
q-binomial coefficients
01-words and inversions
First q-binomial theorem
11. lecture, 20.05.2021
Subspaces of q-vectorspaces
A second q-binomial theorem
Finite sets and posets
Intersecting families of subsets
Posets and lattices
12. lecture, 25.05.2021
Sperner's Theorem - LYM inequality
Small maximal k-intersecting families
Shadows and a second proof of Sperner's
The Kruskal-Katona Theorem
13. lecture, 27.05.2021
The Lovasz version of Kruskal-Katona

14. lecture, 01.06.2021
Symmetric chain decompositions
Symmetric chain decompositions for multisets
Symmetric chain decomp. and pairing brackets
An application to Dedekind's problem
Orthogonal chain decompositions
Two orthogonal chain decompositions for Bn
A probability application of orthogonal chain decompositions
15. lecture, 03.06.2021
Duality theorems
Dilworth's Theorem
König-Egervary matching theorem
Equivalence with Dilworth's
Lemma of Erdöos-Szekeres
16. lecture, 08.06.2021
Tilings
Domino tilings - rectangles and almost rectangles
Tilings with Vs (L-Trominos)
Necessary conditions
Crit 1: divisibility
Crit 2: coloring conditions
tilings with Ts and sticks
Crit 3: homology criterion
free abelian groups and reductions
17. lecture, 10.06.2021
The homology group of Ls (L-tetrominoes)
The power of homology arguments
Aztec diamond A(k) and tilings with Zs (skew-tetrominoes)
coloring argument for k = 1,2 mod 4
no homology argument for k = 0,3 mod 4
18. lecture, 15.06.2021 >
Crit 4: homotopy criterion
Proof for the homotopy criterion
Ex: homotopy can be more powerful than homology
Aztec diamond tilings with Zs
Counting tilings
The Aztec tiling theorem
domino shuffling - sketch of the proof
19. lecture, 17.06.2021
Schröder numbers and small Schröder numbers
Bijection: tilings of A(n) <-> families on n nonintersecting Schröder paths
systems on n nonintersecting paths, Schröder and small Schröder
Lemma of Lindström, Gessel-Viennot
The proof of the  Aztec tiling theorem
The proof of the Lemma of Lindström, Gessel-Viennot
Cancellation of intersecting paths systems via involution
20. lecture, 22.06.2021
Cauchy-Binet formula from the LGV Lemma
Polya Theorie: Counting with symmetries
Necklaces and colored cubes - two introductory examples
Permutation groups and the cycle index
21. lecture, 24.06.2021
The Lemma of Cauchy-Frobenius-Burnside
Polya's first theorem: counting orbits of RD
Weights on R and the induced weight on RD
Polya's fundamental theorem: counting orbits with weights
22. lecture, 29.06.2021
Design Theory
Sλ(t,k,v) designs
Some examples and constructions
Arithmetic conditions
Fisher's inequality

23. lecture, 01.07.2021
Kirkman's problem and a solution
Steiner triple systems with v = 3 mod 6
A construction based on the sharp transitivity of
PGL(2,q) on ordered triples
24. lecture,06.07.2021
Möbius inversion
Incidence algebra of a poset
Zeta function and  Möbius function
Möbius function of chains and products
Inclusion-Exclusion, an example
25. lecture, 08.07.2021
Counting k-covers
(An application in 'exact exponential algorithms')
The Fast-Zeta transform
Catalan numbers
5 Catalan families
Another 5 Catalan families
some bijections

26. lecture, 13.07.2021
More Catalan families
some bijections
Determining the numbers
cycle lemma
reflection principle
symmetric chain decompositions
Narayana numbers via LGV Lemma
27. lecture, 15.07.2021