Discrete Mathematics I SoSe17

Instructors

Course Schedule

Topics

The course will cover a selection from the following topics:

Enumerative Combinatorics

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

Final Exam and Requirements

Exercises

Homework assignment will be posted here.

• Sheet 0 (not to be submitted)
• Sheet 1, Sheet 1 - Sol. sketchs
• Sheet 2, Sheet 2 - Sol. sketchs
• Sheet 3, Sheet 3 - Sol. sketchs Sheet 3 - Some scanned sol.
• Sheet 4, Sheet 4 - Sol. sketchs Sheet 4 - Some scanned sol.
• Sheet 5, Sheet 5 - Sol. sketchs
• Sheet 6, Sheet 6 - Sol. sketchs Sheet 6 - Some scanned sol.
• Sheet 7, Sheet 7 - Some scanned sol.
• Sheet 8, Sheet 8 - Sol. sketchs
• Sheet 9, Sheet 9 - Some scanned sol.
• Sheet 10
• Sheet 11,
• Sheet 12,
• Sheet 13, (not to be submitted)

Here are more exercises covering the first part of the course.

• Supplementary Exercises, (Corrected some mistakes, July 13th)

Here is a Formative Midterm exam to assess your progression.

• Formative Exam, Formative Exam Solutions

Course Plan

These lectures notes may contain typos or mistakes. If you find a significant mistake, please let me know.

• Week 1 (18-19 April): Numbers, Equinumerousity, Addition-Multiplication principles, Bijective Proof ([MN, Ch. 1])
• Week 2 (25-26 April): Bijective Proof, Binomial Theorem, Inclusion-Exclusion Principle and Pigeonhole Principle ([A, Ch. 2], [B, Ch. 1,3,4], [MN, Ch. 3], [Br, Ch. 2,6 & 8])
• Week 3 (2-3 May): The Twelvefold Way: Integer partitions, Set-partitions, compositions, Stirling numbers, Bell numbers ([St, 1.4], [B, Ch. 5], [A, 1.2 to 1.4], [Br, Ch.3])
• Week 4 (9-10 May): Multinomial coefficients, weak compositions, Ferrers diagrams, Solving recurrence relations (Iteration and Char. polyn. Methods) ([B, 4.2], [A, 3.2], [MN, 12.3], [Br, Ch. 7.1-2])
• Week 5 (16-17 May): Solving Rec. Rel. (Symbolic Differenciation and undetermined Coeff. Methods) Formal Power Series: Definitions and Operations. Generating Functions: basic examples. ([A, 3.1], [Br, Ch. 7.3-4], [MN, 12.1-2], [St, 4.1-2], [B, Ch. 8.1])
• Week 6 (23-24 May): Applications of Generating Functions to enumeration. Recurrence relations. Catalan numbers. Exponential Generating Functions. ([MN, 12.3-7], [St. 4.1-3], [Br. 7.4-7], [B. Ch. 8], [A. Ch. 3])
• Week 7 (30-31 May): Posets: Definitions and properties, constructions, examples, Lattices ([B. Ch. 16], [MN, Ch. 2], [St, Ch. 3])
• Week 8 (6-7 June): Examples of lattices, Incidence Algebra, Delta, Zeta and Möbius Functions, Möbius Inversion formula, Examples ([B. Ch. 16], [MN, Ch. 2], [St, Ch. 3])
• Week 9 (13-14 June): Incidence structures: Definitions, Examples, Adjacency and Incidency matrices, regularity, connectedness, chain, cycles, subgraphs, ([B. Ch. 9], [MN, Ch. 4], [Br. Ch.11], [A. Ch. 6])
• Week 10 (20-21 June): Graph morphisms, (semi-)Eulerian graphs, (semi-)Hamiltonian graphs, Ore and Dirac's Theorems, Characterization of trees, Cayley's Theorem on labeled trees. ([Br. Ch.11], [MN, Ch.4-5], [A. Ch. 6-7], [B. Ch.9-10])
• Week 11 (27-28 June): Algorithms: Minimal Spanning Tree, Growing a tree from a root, BFS, DFS, Kruskal algorithm, Dijkstra's Algorithm ([A. Ch. 7], [B. Ch. 10], [MN. Ch. 5.3-4])
• Week 12 (4-5 July): Matchings in Bipartite graphs, Connectivity ([Br. Ch. 9], [A. Ch. 8], [B. Ch. 11])
• Week 13 (11-12 July): Colorings of graphs, Planar graphs [Br. 13.1-3, MN. Ch. 6]
• Week 14 (18-19 July): Chromatic polynomial, Deletion-Contraction principle, 5-Color Theorem [Br. Ch. 13.1-3]

References

• Bona, M., A Walk Through Combinatorics
• Brualdi, R., Introductory Combinatorics
• Aigner, M., Discrete Mathematics (English or German)
• West, D., Introduction to Graph Theory
• Matousek, J., Nesetril, J., An invitation to Discrete Mathematics
• Stanley, R., Enumerative Combinatorics (Volume 1)