VO Kombinatorik WS2010/11 LVNr. 250011

Contact me if you want to take an exam.

Previous exams:
Exam 1, 31.01.2011
Exam 2, 11.02.2011
Exam 3, 28.02.2011
Exam 4, 02.05.2011

Upon request you get an English translation of the problems in the exam. The exam will be written and oral. Answers may be given in German or English. The exam will be written and oral.

Important: It is not sufficient to give correct answers in the written part of the exam. Students will be asked to explain their solutions in the oral part. The list of question should help the students when preparing for the exam. Subject of the exam is the whole material which was presented in the leture.

Here is Chapter 3 of the lecture notes (version 17.02.2011).

winter term 2010/11, lecture on combinatorics, 4 hours a week (6 ECTS). The lecture will be given in English. There is an exercise section (Übung), 2 hours a week (4 ECTS)

Lecture Monday 12:15-13:45, Thursday 10:00-11:45 (with break), C2.09 UZA 4.
Exercise class by Ilse Fischer, Monday 15:15-16:45, C2.07 UZA 4. The problem sheets can be found here.

This is a Mathematica package written by Thomas Blank with a corresponding sample file with which one can compute cycle indicator series for finite permutation groups. The input is a set of permutations which generate the group. The present version of Mathematica 7 at our University does not include such tools, but the new Matheatica 8 is said to have related tools.

Here you find the problem of the hundred prisoners (in German).

Prerequesites: There are no other specific courses required for this lecture as prerequestite, but I am assuming that you are familiar with some elementary notions such as cyclic decomposition of permutations, prime decomposition of integers, the binomial theorem, the solution of linear recursions or group homomorphisms. These are things which you can find in many text books or on Wikipedia. Please contact me if you have further questions.

I have given a silimar course in 2008, see Combinatorics 2008. This time I will use the theory of "combinatorial species".

You do not have to buy any books. But if you are looking for additional literature I recommend:
F. Bergeron, G. Labelle, P. Leroux, "Combinatorial Species and Tree-like Structures", Cambridge University Press 1998.

0 Introduction
0.1 How to prove combinatorial statements
0.2 The number of disjoint k-tuples of subsets of [n]
0.2.1 Standard method
0.2.2 Bijective proof
0.3 Spanning trees of certain classes of graphs

1 Combinatorial Species
1.1 Motivation
1.2 Definition
1.3 Formal power series
1.4 Generating series of species
1.5 Combinatorial equality
1.6 Sum of species
1.7 Product of species
1.8 Sequences without labels
1.9 Sequences with labels (surjections)
1.10 Sustitution of species
1.11 Derivation of species
1.12 Lagrange-Bürmann inversion

2 Redfield-Pólya Theory
2.1 Group representations and Cayley-graphs
2.2 Group actions
2.3 Burnside's Lemma
2.4 Actions on sets of labelled objects
2.5 Cycle indicator series
2.6 Cycle indicator series with weight functions

3 Posets
3.1 Posets, basic definitions
3.2 Lattices, basic definitions
3.3 Theorem of Sperner and symmetric chain decompositions
3.4 Theorem of Dilworth
3.5 The Marriage Theorem
3.6 The Incidence Algebra
3.7 Möbius inversion
3.8 Möbius inversion and sets - The inclusion-exclusion principle
3.9 Möbius inversion in number theory
3.10 Möbius function and topology - Euler-characteristic
3.10.1 Euler-characteristic of order complexes
3.10.2 Euler-characteristic of cell complexes
3.10.3 Euler-characteristic of surfaces

4 Restricted compositions and partitions (by M. Schlosser)


Below you find questions for the exams on 11 and 28 February. For future exams, this list will be different.

1. Sketch one of the proofs (your choice) of how to determine the number of disjoint k-tuples of subsets of an n-element set.
2. Sketch the idea of how to determine the number of spanning trees in the ladder graphs.
3. Give a precise formal definition of a "species of structures" and explain the definition with an example.
4. Determine the expansion of (1-√1-4z)/(2z) around z=0 as formal power series.
5. Define formal power series in general. Define generating and type generating functions of combinatorial species. Define combinatorial equality (isomorohism). Show that the species of linear orders and the species of permutations have the same generating function and show that hey are not isomorphic.
6. Define sum and product of species. What can we say about their generating and type generating functions? Give examples.
7. Detemine the number of triangulations of an n-gon. Formulate and solve the problem using species of structures.
8. Detemine the number of domino-sequences of length n. Formulate and solve the problem using species of structures.
9. Detemine the number of plane rooted trees with n vertices. Formulate and solve the problem using species of structures.
10. Detemine the number of surjections from an n-element set onto an r-element set in general and for specific values of n and r. Express the species of such surjections in terms of the species of sets.
11. Define and explain the composition of combinatorial species.
12. Find identities for the following combinatorial species using sums, products, compositions or derivatives of other combinatorial species. Examples: linear orders, ballots, endofunctions, plane rooted trees, binary plane rooted trees, pre-orders,...
13. Define the derivation of species. Explain examples as partial partitions or linear orders.
14. What is the chain rule for derivations of species? Give at least a heuristic explanation of this rule.
15. Which formal power series have a multiplicative inverse, which have compositional inverses and why?
16. What is Lagrange inversion?
17. Use Lagrange inversion to compute the number of triangulations of an n-gon.
18. Use Lagrange inversion to prove Cayley's formula on the number of labelled trees with or without root.
19. Explain the problem of the 100 prisoners and explain how to solve it.
20. Determine the group and a Cayley-graph for a given presentation.
21. Determine the group and a Cayley-graph for the automorphism group of a given graph.
22. Define group actions. Give examples of actions where the homomorphism is injective, not injective, surjective, not surjective. Define free action and transitive action and give examples.
23. Take two points in the orbit of a group action. Show that the number of group elements that map one point to the other is the same as the cardinality oftheir pointwise stabilizers.
24. Use the result in the previous question to show that the product of the cardinality of a stabiliser of a point with the cardinality of the orbit of that point is the order of the group.
25. Given a geometric object with a group of symmetries. How do we detemine the number of different possibilities to color this object with a given number of colors using the cycle indicator series? State Burnside's Lemma and explain how it is used here.
26. Determine the cycle indicator series for given group actions. The examples will be easy or similar to ones considered in the lecture. In particular consider symmetries of bracelets, necklaces, cube, octahedron and tetrahedron
27. Determine the number isomorphy classes of graphs with four vertices using a cycle indicator series.
28. How can we use weight functions for cycle indicator series to determine colorings where certain colors appear a certain number of times. You will get such an example.
29. Define: poset, maximal element, maximum, supremum, lattice, Jordan-Dedekind-property and rank in a poset. When does a finite poset have a rank function?
30. Define supremum and infimum and show that they are unique if they exist. Show that infimum and supremum are associative.
31. Formulate and prove the Theorem of Sperner on the size of maximal antichains in the subset lattice. You can prove it directly or you can formulate the Theorem of de Bruin on symmetric chain decompositions of the divisor lattice and show that this implies the Theorem of Sperner.
32. Formulate and prove the Theorem of de Bruin on symmetric chain decompositions of the divisor lattice. Why does it also hold for the subset lattice? How does it imply the Theorem of Sperner?
33. Formulate and sketch the proof the Theorem of Dilworth on maximal antichains and minimal chain decompositions.
34. Formulate and prove the Marriage Theorem. You may use the Theorem of Dilworth here without proving it.
35. Define the incidence algebra of a poset and show that it is isomorphic to a subalgebra of the upper triangular matrices.
36. When does an element of the incidence algebra have an inverse? Show how to compute it with an explicite formula.
37. How can we compute the number of chains of a given length between two given points and how can we compute the total number of chains in a finite poset between two given points?
38. Define the Zeta-function and the Möbius-function. Derive a recursive formula with which you can compute the Möbius-function and use it to compute single values for given examples of posets.
39. You will get a concrete example of a poset. Compute the matrix of the Möbius-function. To check that you did that correctly, multiply it with the matrix of the Zeta-function and show that you obtain the unity matrix.
40. What is a dual theorem on posets? How do obtain such theorems? You will get a theorem on posets and you will be asked to formulate the dual theorem, such as the dual Theorem of Weisner.
41. Formulate one of the Möbius-inversion formulas. Use it to prove the Inclusion-exclusion principle.
42. Prove the principle of inclusion and exclusion using Möbius-inversion.
43. Define a simplicial complex and its Euler characteristic. Define the order-complex of a poset. Determine the Euler characteristic of the order complex of a given poset. What does this have to do with the Möbius-function?
44. Define a cell-complex. Determine the Euler characteristic of a cell-complex that generates a given topological space. You will get an example that we have discussed in the lecture and which you can find in the lecture notes.

You do not have to reproduce the proofs of the following theorems and the corresponding lemmas in the written part of the exam, but you have to explain them in the oral exam using lecture notes:
a) Lagrange inversion for Laurent series
b) Burnside's Lemma
c) Möbius inversion formula, both proofs
d) Weisner's Theorem