Instructors Course Schedule Topics Final Exam and Requirements Exercises References Course Progress 
(Images by Mike Sollami) 
Tibor Szabó  Shagnik Das  
Arnimallee 3, Rm 211a  Arnimallee 3, Rm 204  
szabo at math dot fuberlin dot de  shagn  ik@mi.fuber lin.de
Lectures will take place on Tuesdays and Wednesdays from 14:15 to 16:00 in Arnimallee 3, HS 001. You have a choice of two exercise classes: Tuesdays, 16:15 to 18:00, in Takustraße 9, SR 049, or Wednesdays, 10:15 to 12:00, in Arnimallee 6, SR 025/026. 
The course will cover a selection from the following topics:

Final Exam 
The final (written) exam will be held in Hörsaal A, HenryFordBau, from 09:00 to 12:00 on the 26th of July. A makeup exam will be offered in Hörsaal C, HenryFordBau, from 09:00 to 12:00 on the 12th of October. 

Requirements 
A full description of the formalities of the course and the requirements for successfully completing the course can be found here. 
Homework assignments will be posted below, and should be submitted by the end of the Tuesday lectures. Alternatively, they may be submitted to the tutor box of Shagnik Das in Arnimallee 3.
Assignment  Due date  
Sheet 0 (warmup)  Not for submission  
Sheet 1 (regarding the bonus)  26/4/2016  
Sheet 2 (2/5/2016: lower bound on n added to Exercise 1)  3/5/2016  
Sheet 3 (4/5/2016: characteristic polynomial in Exercise 5 corrected)  10/5/2016  
Sheet 4 (11/5/2016: old exercise 3 promoted to Sheet 5)  17/5/2016  
Sheet 5 (20/5/2016: clarification added to exercise 4)  24/5/2016  
Sheet 6 (29/5/2016: footnote numbering corrected)  31/5/2016  
Sheet 7 (3/6/2016: added examples for exercise 1)  7/6/2016  
Sheet 8 (9/6/2016: typo in exercise 1(b) corrected)  14/6/2016  
Sheet 9  21/6/2016  
Sheet 10 (24/6/2016: connectedness condition added to exercise 6)  28/6/2016  
Sheet 11 (1/7/2016: worstcase clarification added to exercise 5)  5/7/2016  
Sheet 12  12/7/2016  
Bonus Sheet  19/7/2016  
Practice Sheet (Solutions [7/10/2016: Solution to 5a corrected])  Not for submission 
The following texts cover most of the material from this course.
M. Aigner  Discrete Mathematics (German and English editions)  
M. Bóna  A Walk Through Combinatorics  
R. Brualdi  Introductory Combinatorics  
R. Diestel  Graph Theory, 4th edition  
L. Lovász, J. Pelikán, K. Vesztergombi  Discrete Mathematics, Elementary and beyond  
J. Matousek, J. Nesetril  Invitation to Discrete Mathematics (German and English editions)  
D. West  Graph Theory 
To learn more about the subject, we recommend the following sources.
M. Aigner  A Course in Enumeration  
B. Bollobás  Combinatorics  
S. Jukna  Extremal Combinatorics  
A. Tucker  Applied Combinatorics  
H. Wilf  Generatingfunctionology 
Some notes are available below.
Elementary counting principles  
The binomial theorem and combinatorial proofs  
The twelvefold ways of counting  
Generating functions I  
Assorted notes on generating functions  
Generating functions II (Updated version; typo at the bottom of page 4: should be c_{n1}, not c_{n})  
Asymptotic estimates  
Estimating binomial coefficients (originally written for Extremal Combinatorics)  
The InclusionExclusion principle (10/6/2016: updated)  
Posets (14/6/2016: updated)  
Möbius inversion  
Examples of Möbius inversion  
The pigeonhole principle and Ramsey's theorem  
Basics of graph theory  
Bipartite, connected and Eulerian graphs  
Extremal problems  
Trees  
Matchings  
Connectivity (Note: Inequality in Proposition on p1 should be reversed)  
Coloring and planar graphs 
Week 
Topics 
References 

1  Elementary counting principles: sum and product rules, doublecounting, combinatorial proofs, binomial identities  Ai Ch 1.1; Bó Ch 34; MN Ch 3.13  
2  Twelvefold ways of counting; set partitions, Stirling numbers of the second kind, polynomial bases; permutations and cycles, Stirling numbers of the first kind  Ai Ch 1.24, Bó Ch 5, 6.1  
3  Number partitions, Ferrers diagrams and identities; Generating functions, Fibonacci sequence, and solving constantcoefficient linear recurrence relations  Bó Ch 8, MN Ch 12.14  
4  Generating functions: key examples, fundamental operations, products of generating functions  Bó Ch 8, MN Ch 12.14  
5  Generating functions for partitions, multivariate generating functions, the pentagonal theorem, composition of general functions  Bó Ch 8, MN Ch 12.14  
6  Exponential generating functions and their products and compositions Asymptotic notation, exponential and factorial estimates 
Bó Ch 8, MN Ch 12.14 MN Ch 3.45 

7  Binomial estimates, rate of growth of the partition function The InclusionExclusion Principle, applications: Euler totient function, derangements 
MN Ch 3.6, 12.7 MN Ch 3.78, Bó Ch 7.12 

8  Posets: Sperner's theorem, Dilworth's theorem; Möbius inversion: general formula, inversion in the Boolean poset  MN Ch 7.2, Bó Ch 16.12  
9  The pigeonhole principle and applications: Chinese Remainder Theorem, ErdősSzekeres theorem, Ramsey's theorem and upper and lower bounds on Ramsey numbers  
10  Graph theory: basic definitions, notation, examples, Handshake lemma, connectedness, Eulerian graphs (statement)  We Ch 1  
11  Graph theory: proof of Euler's Theorem, Bipartite graphs (examples, basic theorems, characterization), Extremal problems (acyclicity, connectivity, Hamiltonicity, trianglefreeness)  We Ch 1.23, 7.2  
12  Equivalent characterisations of trees, spanning trees and Kruskal's algorithm, counting trees via the Prüfer code Matchings and augmenting paths 
MN 8.4, We Ch 2.12 We Ch 3.1 

13  Characterization of maximum matchings, Hall's Theorem, Applications, vertex covers, König's Theorem, connectivity, examples, characterization of 2connected graphs; colourings, chromatic number  MN, We  
14  Lower and upper bound on the chromatic number, their tightness, Mycielski's Construction; curves, planar drawings, planar graphs, plane graphs, Euler's formula, maximum number of edges in a planar graph, Kuratowski's Theorem (no proof), 5colour theorem, 4colour theorem (no proof)  MN, We 