MAT5433

Introduction to basic discrete structures.

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

Catalog entry

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

Contents (1) Relations: Cartesian products, relations, properties of relations, equivalence relations and partitions. (2) Order relations: Partially ordered sets, totally ordered sets, extreme elements (maximum, minimum, maximal and minimal elements), well-ordered sets, maximality principles, Zorn's Lemma, lattices, boolean algebras, circuit design. (3) Graphs: Euler and Hamiltonian paths and circuits, matching, graph coloring, Ramsey’s theorem, trees and searching. (4) Binary operations: Groups and semigroups, products and quotients of groups, other algebraic structures.

Topics List

Week	Topic	Sections from Tucker's book	Subtopics	Prerequisite
1-2	Basic counting principles	10.1-10-2	Permutations, combinations, arrangements with repetitions	MAT1313, CS2233/2231, or instructor consent.
3	Inclusion-Exclusion Principle	2.5-2.7
4	The Pigeonhole Principle	12.1-12.3
Graphs	Asymptotics	13.1-13.2
8	Relations	5.1-6.3
9-10	Discrete structures (graphs, partially ordered sets)	7.1-8.4
10-16	Models of computation	10.1-10.4