|
|
Diskrete Mathematik III - Discrete Mathematics IIISummer 2014 |
|
|
In a nutshell...
Starting: 14 April 2014
Place: Arnimallee 6, SR 032 Seminarraum
Lectures: Monday and Tuesday, 12:00-14:00
More fun: I will be available in my office at Tuesday 10:00-12:00. Of course meetings can be also arranged by appointment.
Prerequisites: graph theory, combinatorics, algebra, complex analysis and probability.
Synopsis: the course will be splitted into two different parts. The course will start studying enumerative problems by means of generating functions, with both exact and asymptotic results.
In particular, we will focus ourselves on studying embedded graphs on the sphere (also called planar maps), showing the existing deep connection between these objects and trees. Consequences in probability theory will be also studied.
In the last weeks of the course we will move to the area of additive Combinatorics, introducing the main techniques and the first results.
Feel free to contact me at jrue at zedat.fu-berlin.de with any questions prior to the start of the course!
Requirements: the requirements of the course are here.
ORAL EXAM: the oral exam will be done the 19th, 21st and 22nd July at Arnimallee 3, office 204. The schedule is also available.
The grading of the oral exam is available here
Methodology: Each person would have an slot of 1 hour for the oral exam. In this 1 hour, the second half (30 minutes) will be devoted properly to the exam. The exam will be done in the office of Junior Prof. Rué (Arnimallee 3, office 204) and will be done by 2 examiners.
Once the person arrives at the time the slot starts, he/she will receive the questions to be developed. It is very important NOT to be delayed in order to make the schedule works fine, and in order to avoid shifts that would be bad for the rest of the students.
Each person will have 30 minutes to prepare answers and structure the exam WITHOUT material. Each person will prepare it in an office near office 204.
There will be three questions:
1.- (5 points): A theoretical question. The list of questions is here. Each person will choose between 2 proposed topics. Each person will have around 15 minutes to present this part and the examiners will ask you. Blackboard and paper to draw pictures will be available.
2.- (4 points): a problem from the homework: a 10 point problem (or part of it) from the homework will be proposed, and each person should be able to explain the main ideas on the blackborad. You will have around 10 minutes to present the main ideas of the solution.
3.- (1 point): an small new question: you will have to think about a new question posted in the exam (small means shorter and easier than the ones in the problem sheet, or a Theoretical question that does not need of computations). You will have around 5 minutes to present the answer.
In all the points the examiners will ask you. Here you have a simulation of what you will find.
MAKE-UP EXAM: The Make-up exam will be done September 16th from 11:00 to 14:00, at SR031 (Arnimallee 6). The material you should now for the Make-up is the following:
- Definitions, statement and proofs of theorems: you should know all the material presented at the lecture.
- Problems from the exercise sheets: you should know how to solve all homework exercises.
- New problems: you should be able to apply the encountered theorems and methods to solve exercises you have possibly never seen.
You could have a look at this "Simulation". In particular, there will be:
- 4 points of theoretical questions.
- 2 points for a problem done in the tutorials.
- 2 points for a problem which requires basic knowledge of the subject.
- 2 points for a problem (with several sections) similar to the problems in homework.
What we have seen so far...
|
When? |
What? |
Scans |
Problems |
|
14/04/14 |
Introduction to the material of Discrete Mathematics III (Stanley, Vol. 1 Chapter 1): Formal power series: definition; sum and product. Inverse and functional inverse. Necessary and sufficient conditions for the existence of inverse and functional inverse. Derivative of a formal power series and consequences. Primitive of a formal power series. Sequences and generating functions (GF). Translation of sequences into GFs. |
|
(Typo corrected in Probl. 4)
|
|
15/04/14 |
(Stanley, Vol. 1 Chapter 4): Rational formal power series. Connection with sequences defined by linear recurrence relations: theorem of characterization in terms of linear recurrences. (Stanley, Vol. 2, Chapter 6): Algebraic formal power series: definition and properties: algebraic fps are closed by sum, product (not proved), inverse, functional inverse and derivative (sketch of the proof). D-finite formal power series and P-recursive sequences: the GF of a P-recursive sequence is D-finite. |
|
|
|
22/04/14 |
(Stanley, Vol. 2, Chapter 6): every algebraic fps is D-finite. Laurent series and the field of fractions of the ring of fps. Residue of a Laurent series. Properties. Extracting coefficients by residue comptuation. Lagrange Inversion Formula. A detailed study of Catalan function (algebricity, algebricity of the derivative, extraction of coefficients, ...) |
||
|
28/04/14 |
(Flajolet& Sedgewick, Chapter 1): The Symbolic Method: combinatorial classes and admissible classes. Ordinary generating function associated to a class. Neutral and atomic class. Admissible constructions: disjoint union, cartesian product, sequence, multiset, powerset and cycle construction. Pointing and substitution. |
||
|
29/04/14 |
(Flajolet & Sedgewick, Chapter 1): multivariate OGF. Examples: words over an alphabet, compositions and partitions, triangulations of a labelled polygon, decomposition of a labelled polygon into k-agons. |
|
|
|
05/05/14 |
(Flajolet & Sedgewick, Chapter 1): More examples: rooted trees (embedded and non-embedded, general and binary, unary-binary trees and Motzkin numbers), Dyck paths. |
||
|
06/05/14 |
Problem Session |
||
|
12/05/14 |
(Flajolet & Sedgewick, Chapter 2): Labelled families and Exponential Generating Functions. Definition of labelled family, and well-labelled objects. Operations: the labelled product. Constructions: union, sequence, set, pointing-substitution and cycle construction. Examples: rooted (embedded and non-embedded) labelled trees. Unrooted labelled trees. |
|
|
|
13/05/14 |
NO session (postponed) |
||
|
19/05/14 |
(Flajolet & Sedgewick, Chapter 2): More examples on labelled families: permutations, cyclic permutations, derrangements and involutions. Mappings and functional graphs. (Flajolet & Sedgewick, Chapter 3): probability distributions over finite sets: parameters and random variables. Getting the k-th factorial moment from the Gfs. Example: getting the expected number of 1's in a uniformly at random binary word of length n. |
(Note: in Problem 4.2 the operator Bo is the pointed operator where we forget about the size of the root) |
|
|
20/05/14 |
Problem session |
|
|
|
26/05/14 |
(Flajolet & Sedgewick, Chapter 4): Analytic techniques in Enumerative Combinatorics: the philosophy. A crash course on complex analysis: differentiability, holomorphicity, analycity and equivalences. Meromorphic and entire functions. Singularities: examples. The complex logarithm. |
A crash course on Complex Analysis (Updated 16/05/14) |
NO Homework! |
|
27/05/14 |
Problem Session |
||
|
02/06/14 |
(Flajolet & Sedgewick, Chapter 4): square root and inverse function theorem in complex analysis. Exponential growth of the coefficients: radius of convergence and the first main principle in Analytic Combinatorics. Examples: surjections, derangements. Lagrangian schemes, hypothesis and position of the singularity in Lagrangian schemes. Example of Catalan numbers. |
|
|
|
03/06/14 |
Problem Session |
||
|
BONUS PROBLEMS – Enumeratives Techniques in Combinatorics |
|||
|
10/06/14 |
EXTRA problem Session : 8:30 at Arnimallee 3, Room 210 |
|
No Homework! |
|
10/06/14 |
Problem Session |
||
|
16/06/14 |
(Flajolet & Sedgewick, Chapter IV.1, IV.5, VI.2, VI.3) Subexponential growth of coefficients: second principle of Singularity Analysis. Examples: rational functions, meromorphic functions. Lagrangian schemes: square-root singularities, Puiseux expansion and singular expansion. Transfer Theorem for singularity analysis. |
(Little correction in Problem 4) |
|
|
17/06/14 |
Problem Session |
||
|
23/06/14 |
(Goulden & Jackson 2.9.4., 2.9.9.) Planar Maps: definition and isomorphism between between maps. Corners in maps. Rooted planar mapsand census of the smallest rooted maps. Root decomposition and equations for the GF of maps |
Little typo corrected in Probl 1 |
|
|
24/06/14 |
Problem Session |
||
|
30/06/14 |
Rooted planar maps: how to solve the equations: the Quadratic Method. The exact formula. The Cori-Vaulequin-Schaeffer Bijection by means of distances: trivial bijection with quadrangulations, origin and distances, local rule for each face, construction of the tree (graph which is indeed a tree). |
||
|
01/07/14 |
Problem session |
||
|
A “simulation” of the Final Exam. The schedule and the theoretical questions in the first part of the oral exam |
|||
|
07/07/14 |
Rooted planar maps: well-labelled trees and its relation with Catalan trees. The inverse construction: trees and the associated polygon. The rule to construct a map. Proof that all faces are quadrangles. Final operation concerning vertices with label 1. |
||
|
08/07/14 |
Problem session |
||
|
14/07/14 |
Problem Session |
||
|
15/07/14 |
Problem Session |
||
|
22/07/14 |
The grading of the oral exam |
||
|
22/07/14 |
A “simulation” of the Make-up Exam |
||
The basic basic reference is the book Flajolet, Sedgewick: Analytic Combinatorics, which can be downloaded for free here. Other references are the following:
Lando,
Zvonkin: Graphs on Surfaces and Their Applications.
Stanley:
Enumerative Combinatorics Vol 1 and 2.
Goulden,
Jackson: Combinatorial Enumeration.
In
the last part of the course (Additive Combinatorics) we will use Tao,
Vu: Additive Combinatorics