MAT4323

Catalog entry

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

Contents

Graph models (Isomorphisms, edge counting, planar graphs), Covering circuits and graph colorings (Euler circuits, Hamilton circuits, graph colorings), Network algorithms (Shortest path, minimum spanning trees, matching algorithms, transportation problems), Ramsey's Theorem and Ramsey numbers.

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

[3] Gary Chartrand and Ping Zhang, A First Course in Graph Theory, Dover Books on Mathematics, 2012.

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.
1-3	Graph models	12.1-12.3	Isomorphism, edge counting, planar graphs.
4-6	Covering circuits	2.1-2.4	Euler circuits, Hamilton circuits, graph colorings, coloring theorems.
8-9	Trees	3.1-3.4	Search trees, spanning trees, the Traveling Salesman Problem
10-12	Network algorithms	4.1-4.5	Shortest path , minimum spanning trees, matching algorithms, transportation problems.	13-14	Network algorithms		Ramsey's Theorem and Ramsey numbers