MAT5433

Catalog entry

Prerequisite: Algebra and Number Systems (MAT 1313), or Discrete Mathematical Structures (CS 2233/2231), or instructor consent.

Contents (1) Basic counting principles: Permutations, combinations, binomial coefficients, arrangements with repetitions. (2) The Inclusion-Exclusion principle. (3) Graph models: Isomorphisms, edge counting, planar graphs. (4) Covering circuits and graph colorings: Euler circuits, Hamilton circuits, graph colorings, Ramsey's theorem (5) Network algorithms: Shortest path, minimum spanning trees, matching algorithms, transportation problems. (6) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles.

Sample textbooks

[1] Vladlen Koltun, Discrete Structures, Lecture Notes, Stanford University, 2008. Freely available online here

[2] Alan Tucker, Applied Combinatorics, Freely available online here

Topics List

Week	Topic	Sections from Tucker's book	Subtopics	Prerequisite
1-2	Basic counting principles	5.1-5.5	Permutations, combinations, binomial coefficients, arrangements with repetitions	MAT1313, CS2233/2231, or instructor consent.
3	Inclusion-Exclusion Principle	8.1-8.2	Counting with Venn diagrams.
4-6	Graph models	12.1-12.3	Isomorphism, edge counting, planar graphs.
7-8	Covering circuits	2.1-2.4	Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
9-10	Trees	3.1-3.4	Search trees, spanning trees, the Traveling Salesman Problem
11-13	Network algorithms	4.1-4.5	Shortest path , minimum spanning trees, matching algorithms, transportation problems.