Listed below are the administrative details regarding the course.
If you are interested in taking this course, please make sure you register in the Whiteboard system. (Instructions for registration, and for non-FU students.) It is important to do this as soon as possible, so that we can contact you if needed.
In keeping with the university's coronavirus guidelines and maintaining a responsible level of social distancing, all course activities will take place online through the Cisco Webex Meetings platform. Please be sure to have installed and familiarised yourself with any necessary software in advance. Information for setting up an account for FU students can be found in the ZEDAT portal. Once installed, you can test your configuration here.
Starting from the 21st of April, lectures will take place on Tuesdays and Wendesdays, from 14:15 to 15:45 and the exercise classes on Tuesdays from 16:00 to 17:30 and Wendesdays from 08:30 to 10:00. The links to the Webex meetings will be available in the Whiteboard system.
| Tibor Szabó | Michael Anastos | ||
| Arnimallee 3, Room 211a | Arnimallee 3, Room 202 | ||
| szabo at math dot fu-berlin dot de | manastos at mi dot fu-berlin dot de |
A full description of the formalities of the course and requirements for successfully completing the course can be found here.
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, posets, matroids.
Graph Theory: Trees, matchings, connectivity, planarity, colourings.
Exercise sheets will be posted on Whiteboard every Wednesday, and should be submitted before 23:59 on Monday of the following week.
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 |
| Week 2 | The Inclusion-Exclusion Princible:derangements, 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 |
| Week 3 | integer partitions, Fibonacci sequence, its generating function and formula | Bó Ch 8, MN Ch 12.1-3 |
| Week 4 | generating functions, basic operations, examples, product, Catalan numbers | Bó Ch 8, MN Ch 12.1-4 |
| 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 | MN Ch 3.4-6 |
| Week 7 | The pigeonhole principle and applications: Chinese Remainder Theorem, Erdős-Szekeres theorem, Ramsey numbers | MN Ch 11, Bó Ch 1 |
| Week 8 | Posets: Sperner's theorem, Dilworth's theorem , Graph theory: basic definitions, notation, examples | MN Ch7.2 We Ch 1 |
| Week 9 | Graph theory: proof of Euler's Theorem, Bipartite graphs (examples, basic theorems, characterization) | We Ch 1.2 |
| Week 10 | Extremal problems (acyclicity, connectivity, Hamiltonicity, triangle-freeness), Trees: characterization, Kruskal's algorithm | We Ch 1.3 & 2.1-3 |
| Week 11 | Trees: Prufer Codes, Matchings: Berge's Theorem, Hall's Theorem, Petersen's Theorem on 2-factors, Konig's Theorem | We Ch 2.1-2, 3.1 |
| Week 12 | Colorings: motivation, defintions, examples, simple lower bounds, tightness, perfect graphs, Mycielski's Construction | We Ch 5.1, 8.1 |
| Week 13 | Planar Graphs: planar drawings, 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, Six Color Theorem, Five Color Theorem, Four Color Theorem (no proof) | We Ch 6.1-3 |