Discrete Mathematics I
Summer 2016
|
Instructors Course Schedule Topics Final Exam and Requirements Exercises References Course Progress |
 (Images by Mike Sollami) |
Instructors
| Tibor Szabó | Shagnik Das | ||
| Arnimallee 3, Rm 211a | Arnimallee 3, Rm 204 | ||
| szabo at math dot fu-berlin dot de | shagnik@mi.fu-berlin.de |
Course Schedule
| 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. |
Topics
The course will cover a selection from the following topics:
|
Final Exam and Requirements
Final Exam |
The final (written) exam will be held in Hörsaal A, Henry-Ford-Bau, from 09:00 to 12:00 on the 26th of July. A make-up exam will be offered in Hörsaal C, Henry-Ford-Bau, 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. |
Exercises
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 (warm-up) | 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: worst-case 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 |
References
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 cn-1, not cn) | ||
| Asymptotic estimates | ||
| Estimating binomial coefficients (originally written for Extremal Combinatorics) | ||
| The Inclusion-Exclusion 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 |
Course Progress
Week |
Topics |
References |
||
| 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 | ||
| 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 | ||
| 3 | Number partitions, Ferrers diagrams and identities; Generating functions, Fibonacci sequence, and solving constant-coefficient linear recurrence relations | Bó Ch 8, MN Ch 12.1-4 | ||
| 4 | Generating functions: key examples, fundamental operations, products of generating functions | Bó Ch 8, MN Ch 12.1-4 | ||
| 5 | Generating functions for partitions, multivariate generating functions, the pentagonal theorem, composition of general functions | Bó Ch 8, MN Ch 12.1-4 | ||
| 6 | Exponential generating functions and their products and compositions Asymptotic notation, exponential and factorial estimates |
Bó Ch 8, MN Ch 12.1-4 MN Ch 3.4-5 |
||
| 7 | Binomial estimates, rate of growth of the partition function The Inclusion-Exclusion Principle, applications: Euler totient function, derangements |
MN Ch 3.6, 12.7 MN Ch 3.7-8, Bó Ch 7.1-2 |
||
| 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.1-2 | ||
| 9 | The pigeonhole principle and applications: Chinese Remainder Theorem, Erdős-Szekeres 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, triangle-freeness) | We Ch 1.2-3, 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.1-2 We Ch 3.1 |
||
| 13 | Characterization of maximum matchings, Hall's Theorem, Applications, vertex covers, König's Theorem, connectivity, examples, characterization of 2-connected 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), 5-colour theorem, 4-colour theorem (no proof) | MN, We |