Discrete Mathematics

Discrete Mathematics – 60610

This course provides an introduction to the questions of existence, structure and enumeration of discrete mathematical objects. Topics include:

1. Enumeration — basic counting principles (including permutations, combinations, compositions, pigeon-hole principle and inclusion-exclusion), basic counting sequences (such as binomial coefficients, Catalan numbers and Stirling numbers), and recurrence relations and generating functions.
2. Structure and existence — Graphs (including trees, connectivity, Euler trails and Hamilton cycles, matching and coloring), partially ordered sets and lattices, basic Ramsey theory, error detecting and correcting codes, combinatorial designs, and techniques from probability and linear algebra.

Other topics chosen by the instructor may be included if time permits. The course will be at the level of the following books:

• Stasys Jukna, Extremal combinatorics: With Applications in Computer Science
• Peter Cameron, Combinatorics: Topics, Techniques, Algorithms
• J.H. van Lint and R.M. Wilson, A Course in Combinatorics