Links:    Home     Homework     Exams     Calendar     Syllabus     Resources

## Math 154: Discrete Mathematics and Graph Theory Winter 2020, Prof. Tesler Calendar

### Updated 3/11/20

Note: This calendar is approximate and is subject to revision.
Chapter numbers are for the class textbook by Verstraete.

Lectures will be a mix of chalkboard and slides.
If there are slides, they'll be posted below.
Slides are subject to revision.

 Week 1 Jan 6 Syllabus Introduction to Graph Theory (slides 1-21) Chapter 1 (1.1, 1.3-1.6) and Appendices A.2-A.3 Ch. 1.2 is optional; it's an overview of topics in the book. Jan. 8 slides continued (21-37) Jan. 10 slides continued (rest of slides) Subgraphs, walks, Eulerian and Hamlitonian graphs (slides 1-17) Chapters 1.7 and 2 (2.1-2.6; skip 2.7) Week 2 Jan. 13 slides continued (18-35) Jan. 15 slides continued (36-47) Jan. 17 slides continued (rest of slides) Week 3 Jan. 20 Martin Luther King, Jr. Holiday Jan. 22 Trees (slides) Chapter 3.1 Spanning tree algorithms (slides 1-3), (worksheets) Chapter 3.2-3.4 Please print out the worksheets at full size to facilitate note taking in lecture. Jan. 24 slides continued (4-51) + worksheets The DFS example on the slides has a mistake, so I used worksheets on the projector instead. There were also several other examples on the worksheets on the projector. See the 1/24 and 1/27 podcasts to review it. Week 4 Jan. 27 slides continued (rest of slides and worksheets) Weighted graph algorithms (slides 1-14) Chapter 3.5-3.6 Jan. 29 slides continued (14-35) Jan. 31 slides continued (rest of slides) Connectivity Will be on the chalkboard, not on slides. Chapter 4.4-4.5 and 4.7. Skip other parts of Chapter 4 for now (may do later in the quarter if time permits). Campuswide deadline to drop without a "W" Week 5 Feb. 3 Chapter 4 continued Example for question asked in class about a graph with λ(G)<δ(G), namely, 1<2: (drawing) Matchings Chapter 5 intro to matchings (on chalkboard) Feb. 5 Chapter 5.1: Independent sets, matchings, vertex and edge covers Feb. 7 Midterm Week 6 Feb. 10 Matchings: Hall's Theorem, applications, and generalizations (slides 1-24) [slides revised 2/10 after class] Chapter 5.2-5.8 Feb. 12 slides continued (25-39, 57-61) Feb. 14 slides continued (rest of slides) Campuswide deadline to drop with a "W" Week 7 Feb. 17 Presidents' Day Holiday Feb. 19 Vertex and Edge Colorings (revised slides 1-24, 45-48) [slides revised again 2/23] Chapter 6 Feb. 21 slides continued (25-39) Week 8 Feb. 24 slides continued Planar Graphs (slides 1-16) Chapter 7 Covering 7.1-7.3 in full, and parts of 7.4 and 7.6-7.8. Skipping 7.5. Feb. 26 slides continued (17-34) Feb. 28 slides continued (rest of slides) Week 9 Mar. 2 The Max-Flow Min-Cut Theorem (slides 1-31) Chapter 8 Mar. 4 slides continued (32-48) Mar. 6 slides continued (rest of slides) Stable Matchings: The Gale-Shapley Algorithm (slides 1-8) Week 10 Mar. 9 slides continued (up to 31) Mar. 11 slides continued (rest of slides) Extremal Graph Theory (slides 1-26) Chapter 9-9.2 (+ Ramsey Numbers, not in the book) Mar. 13 slides continued Week 11 Wed. Mar. 18 Final exam, 3-6 p.m.