20476 Discrete Mathematics: Set Theory, Combinatorics and Graph Theory 1

Credits: 4 intermediate credits in Mathematics

Prerequisites: none

Recommended: Introduction to Mathematics

Authors: Abraham Ginzburg, Zeev Nutov, Itai Hareven

This course presents mathematical concepts and methods that provide a background for the study of Computer Science and contributes to the development of students’ mathematical sophistication.

Topics: Brief introduction to logic – Propositions, connectives, truth tables. Variables, predicates, quantifiers. Important identities. Set theory – Sets and their elements, subsets, operations on sets. The power set. Cartesian products. Relations. Multiplication and inversion of relations. Equivalence relations, partitions, quotient sets. Partial and linear orderings. Functions. Mathematical induction. Countable sets and the cardinality of the set of real numbers. Cantor-Schröder-Bernstein’s theorem, Cantor’s theorem. Cardinals: addition, multiplication and exponentiation. Combinatorics – The principles of addition and multiplication. Permutations, combinations and variations with and without repetitions. Newton’s binomial formula and identities involving binomial coefficients. The inclusion-exclusion principle. Total disorders. Euler’s function. The pigeonhole principle. Recursive relations and generating functions. Graph theory – Graph: degree, path, circle, distance, diameter, connectivity, subgraph, full graph, bipartite graph. Characterization of bipartite graphs. Trees. Cayley’s theorem. Eulerian & Hamiltonian paths and circuits: Euler’s theorem, Dirac’s theorem. Pairings, coverings, cliques & independent sets: Berge’s theorem, Hall’s theorem. Coloring: Brooks’ theorem, Euler’s formula for planar graphs, the 5-color theorem.

---

1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.