
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:0014:00
More fun: I will be available in my office at Tuesday 10:0012: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.fuberlin.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 19^{th}, 21^{st} and 22^{nd} 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.
MAKEUP EXAM: The Makeup exam will be done September 16th from 11:00 to 14:00, at SR031 (Arnimallee 6). The material you should now for the Makeup 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). Dfinite formal power series and Precursive sequences: the GF of a Precursive sequence is Dfinite. 


22/04/14 
(Stanley, Vol. 2, Chapter 6): every algebraic fps is Dfinite. 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 kagons. 


05/05/14 
(Flajolet & Sedgewick, Chapter 1): More examples: rooted trees (embedded and nonembedded, general and binary, unarybinary 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 welllabelled objects. Operations: the labelled product. Constructions: union, sequence, set, pointingsubstitution and cycle construction. Examples: rooted (embedded and nonembedded) 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 kth 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 B^{o }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: squareroot 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 CoriVaulequinSchaeffer 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: welllabelled 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 Makeup 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