# 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. |