CMSC 475: COMBINATORICS AND GRAPH THEORY

Catalog Description

General enumeration methods, difference equations, generating functions. Elements of graph theory, matrix representations of graphs, applications of graph theory to transport networks, matching theory and graphical algorithms. Listed also as MATH 475.

Prerequisites

MATH 240 and MATH 241.

Topics

Combinatorics (7 weeks)
- The pigeonhole principle (Chap. 2)
- Basic counting principles: permutations and combinations (Chap. 3)
- Binomial coefficients (Chap. 4)
- Inclusion-exclusion principle (Chap. 5)
- Recurrence relations (Chap. 6)
- Generating Functions (Chap. 7)
Graph theory (7 weeks)
- Introduction (Chap. 10)
- Chromatic number, connectivity, and other graphical parameters (Chap. 11)

Course Text

Richard A. Brualdi, Introductory Combinatorics, North Holland.

Typical Grading and Workload

Exams and homeworks.