Lectures will take place in Arinmallee 3, Hs 001 and exercise classes will take place in Arnimallee 6, SR 007/008 on Tuesdays and in Arnimallee 3, SR 119 on Wednesdays.
The lectures will be on Tuesdays and Wednesdays from 14:15 to 15:45.
The exercise classes will be on Tuesdays from 16:15 to 17:45 and Wednesdays from 10:30 to 12:00.
Office hours are on Mondays, from 14:00 to 15:00, and Thursdays, from 14:00 to 15:00, in Arnimallee 3, Room 206.
| Tibor Szabó | Tamás Mészáros | Anurag Bishnoi | ||
| Arnimallee 3, Room 211a | Arnimallee 3, Room 205 | Arnimallee 3, Room 206 | ||
| szabo at math dot fu-berlin dot de | tamas dot meszaros at fu-berlin dot de | anurag.2357 at gmail dot com |
A full description of the formalities of the course and requirements for successfully completing the course can be found here.
The final exam will take place on Wednesday, July 25th 2018, from 13:00 to 16:00, in Hs 1b Hörsaal (Habelschwerdter Allee 45). (results)
A make-up exam will be offered on Wednesday, October 10th 2018, from 10:00 to 13:00, in HFB/C Hörsaal (Garystr. 35-37). (results
Over the course of this semester, we shall cover the following topics:
Enumerative Combinatoric: Elementary counting methods, double-counting, pigeonhole principle, recursions, generating functions, inclusion-exclusion, inversion, Polya theory.
Discrete Structures: Graphs, set systems, designs, posets, matroids.
Graph Theory: Trees, matchings, connectivity, planarity, colourings.
Exercise sheets will be posted below every Wednesday, and should be submitted before 16:15 on Tuesday of the following week.
| Assignment | Due date | Comments |
|---|---|---|
| Review sheet | Not for submission | |
| Sheet 1 | 24/04/2018 | |
| Sheet 2 | 2/05/2018 | |
| Sheet 3 | 8/05/2018 | |
| Sheet 4 | 15/05/2018 | 11.05: correction to Exercise 2 |
| Sheet 5 | 22/05/2018 | |
| Sheet 6 | 29/05/2018 | |
| Sheet 7 | 05/06/2018 | |
| Sheet 8 | 12/06/2018 | 11.06: correction to Exercise 4 |
| practice exam | 19/06/2018 | solutions |
| Sheet 9 | 26/06/2018 | |
| Sheet 10 | 3/07/2018 | |
| Sheet 11 | 10/07/2018 | |
| Sheet 12 | 17/07/2018 | |
| Sheet 13 | 01/08/2018 | Bonus sheet |
As we make our way through the semester, we will provide below a brief review of the topics covered each week.
| Week | Topics | References |
|---|---|---|
| Week 1 | Elementary counting principles: sum and product rules, double-counting, combinatorial proofs, binomial identities | Ai Ch 1.1; Bó Ch 3-4; MN Ch 3.1-3 lecture notes |
| Week 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.2-4, Bó Ch 5, 6.1 lecture notes (updated 5.5) |
| Week 3 | integer partitions, Fibonacci sequence, its generating function and formula | Bó Ch 8, MN Ch 12.1-3 lecture notes (11.5: updated) |
| Week 4 | generating functions, basic operations, examples, product, Catalan numbers | Bó Ch 8, MN Ch 12.1-4 lecture notes |
| Week 5 | Exponential generating functions and their products and compositions | Bó Ch 8, MN Ch 12.1-4 |
| Week 6 | Asymptotic notation, exponential and factorial estimates, Binomial estimates, rate of growth of the partition function, The Inclusion-Exclusion Principle | MN Ch 3.4-6 |
| Week 7 | The Inclusion-Exclusion Principle:derangements, Posets: Sperner's theorem, Dilworth's theorem | MN Ch 7.2, Bó Ch 16.1-2 lecture notes |
| Week 8 | Mobius inversion, The pigeonhole principle and applications: Chinese Remainder Theorem, Erdős-Szekeres theorem, Ramsey numbers | MN Ch 11, Bó Ch 1lecture notes 1 lecture notes 2 |
| Week 9 | Ramsey numbers, Graph theory: basic definitions, notation, examples, Handshake lemma | We Ch 1lecture notes 1lecture notes 2 |
| Week 10 | Graph theory: proof of Euler's Theorem, Bipartite graphs (examples, basic theorems, characterization), Extremal problems (acyclicity, connectivity, Hamiltonicity, triangle-freeness) | We Ch 1.2-3, 7.2 lecture notes |
| Week 11 | Trees: characterization, Kruskal's algorithm, Prufer codes, Matchings: Berge's theorem, Hall's theorem | MN 8.4, We Ch 2.1-2, We Ch 3.1 Trees Matchings |
| Week 12 | Matchings: Petersen's Theorem on 2-factors, Konig's Theorem, Colorings: motivation, defintions, examples, simple lower bounds, tightness, perfect graphs, Mycielski's Construction | Colorings |
| Week 13 | proof of Mycielski's construction, planar drawings, planar graphs, plane graphs, Euler's formula, maximum number of edges in a planar graph, Kuratowski's Theorem (no proof), platonic solids, dual of a graph, maximal planar graphs | planar graphs |
| Week 14 | Six Color Theorem, Five Color Theorem, Four Color Theorem (no proof), proof of Kuratowski's theorem | notes |