Math 154 (Discrete Mathematics)

✍ Scribed by Steven V. Sam

• Year: 2019
• Tongue: English
• Leaves: 47
• Edition: version 2019-03-19
• Category: Library

✦ Table of Contents

1. Induction
   1.1. Weak induction
   1.2. Strong induction
2. Elementary counting problems
   2.1. Bijections
   2.2. Sum and product principle
   2.3. Permutations and combinations
   2.4. Words
   2.5. Choice problems
3. Binomial theorem and generalizations
   3.1. Binomial theorem
   3.2. Multinomial theorem
4. Inclusion-exclusion
5. Graph theory, introduction
   5.1. Eulerian trails
   5.2. Directed graphs
   5.3. Hamiltonian cycles
   5.4. Graph isomorphisms
6. Trees
   6.1. Definition and basic properties
   6.2. Adjacency matrix
   6.3. Deletion-contraction
   6.4. Matrix-tree theorem
   6.5. Minimum-weight spanning trees
7. Coloring and matching
   7.1. Colorings and chromatic polynomials
   7.2. Bipartite graphs
   7.3. Matchings
   7.4. Stable matchings
8. Planarity
   8.1. Definitions
   8.2. Some equations and inequalities
   8.3. Obstructions to planarity
   8.4. Chromatic numbers of planar graphs
9. Ramsey theory
   9.1. Pigeon-hole principle
   9.2. Ramsey's theorem for graphs
   9.3. Lower bounds on Ramsey numbers