|
|
Schedule for weeks 1 through 16 |
| Wk |
Day |
Date |
Topic | Resources | Events |
|
| 1 | Tue | Jan 10 | Course Introduction
Graphs
Graph Terminology | CGT 1-1.1.2 | 1.1.1: 3,4
1.1.2: 1,2,4,5,9, 12,15,16 | |
|
| Thu | Jan 12 | Special Types of Graphs | CGT 1.1.3 | 1.1.3: 1,5,6,8,9,10 |
|
| 2 | Tue | Jan 17 | Distance in Graphs | CGT 1.2 | 1.2.1: 1,2,6,8,11
1.2.2: 1,2,4,6
1.2.3: 2,3 | |
|
| Thu | Jan 19 | Trees | CGT 1.3-1.3.3 | HW 1 due
1.3.1: 1,2,3
1.3.2: 1,3,5,8
1.3.3: 1,4,5,7 |
|
| 3 | Tue | Jan 24 | Counting Trees | CGT 1.3.4 | 1.3.4: 2,3,4,5,6 | |
|
| Thu | Jan 26 | Trails, Circuits, Paths, and Cycles | CGT 1.4-1.4.2 | HW 2 due
1.4.1: 2,3
1.4.2: 1,2,4,5,7,8 |
|
| 4 | Tue | Jan 31 | Hamiltonian Paths and Cycles
Three Open Problems | CGT 1.4.3-1.4.4 | HW 3 due
1.4.3: 1,4,6,7,9,12
1.4.4: 1,2,3,4 | |
|
| Thu | Feb 02 | Planarity
Euler's Formula and Beyond | CGT 1.5-1.5.2 | 1.5.1: 1,2,5,6,8
1.5.2: 1,2,4,7,9,10
Note: add "with triangular regions" to 10.
(typo) |
|
| 5 | Tue | Feb 07 | Regular Polyhedra
Kuratowski's Theorem
| CGT 1.5.3-1.5.4 | HW 4 due
1.5.3: 1,2
1.5.4: 1,2,4 | |
|
| Thu | Feb 09 | Colorings | CGT 1.6-1.6.2 | 1.6.1: 1,2,4,5
1.6.2: 2,5,6,7 |
|
| 6 | Tue | Feb 14 | No Class | | Winter Recess | |
|
| Thu | Feb 16 | The Four Color Problem
Chromatic Polynomials | CGT 1.6.3-1.6.4 | 1.6.3: 1,3,5
1.6.4: 1,3,4 |
|
| 7 | Tue | Feb 21 | Matchings
Hall's Theorem and SDRs | CGT 1.7-1.7.2 | HW 5 due
1.7.1: 1,2
1.7.2: 1,2,3,4*,6
*4 has typo. Need n≥2 and |Si|=n-1 | |
|
| Thu | Feb 23 | Nothing | | Icepocalypse 2023: No class |
|
| 8 | Tue | Feb 28 | The König-Egerváry Theorem
Perfect Matchings | CGT 1.7.3-1.7.4 | 1.7.3: 1,2,3(hard?)
1.7.4: 1,2,4,5,6,7 | |
|
| Thu | Mar 02 | Midterm Exam | | |
|
| 9 | Tue | Mar 07 | Ramsey Theory | CGT 1.8 | 1.8.1: 1,3,4
1.8.2: 1,2,4,5
1.8.3: 2,3,4 | |
|
| Thu | Mar 09 | Combinatorics:
Some Essential Problems | CGT 2-2.1 | HW 6 due
2.1: 1,4,11,12,14 |
|
| 10 | Tue | Mar 14 | Binomial Coefficients | CGT 2.2 | 2.2: 1,2,4,6,7bd,8 | |
|
| Thu | Mar 16 | Multinomial Coefficients | CGT 2.3 | HW 7 due
2.3: 1,2,3,4,9ace,11
Typo in 4: sum indices are missing "=n" |
|
|
Spring Break Week |
|
| 11 | Tue | Mar 28 | The Pigeonhole Principle | CGT 2.4 | HW 8 due
2.4: 1,3,4,5,7,9,13 | |
|
| Thu | Mar 30 | The Principle of Inclusion and Exclusion | CGT 2.5 | 2.5: 2,4,6,8,12
Error in 4: change 250 to 230 |
|
| 12 | Tue | Apr 04 | Generating Functions | CGT 2.6-2.6.2 | HW 9 due
2.6: 1,2
2.6.1: 1,2,4
2.6.2: 1,3,5,8 | |
|
| Thu | Apr 06 | Changing Money
Fibonacci Numbers | CGT 2.6.3-2.6.4 | 2.6.3: 1,3,9,10
2.6.4: 1,2,5bd,10 |
|
| 13 | Tue | Apr 11 | Recurrence Relations
Catalan Numbers | CGT 2.6.5-2.6.6 | 2.6.5:1,2ad,6,7
2.6.6: 2,3,4 | |
|
| Thu | Apr 13 | Counting ways to trianglalize n-gons | | |
|
| 14 | Tue | Apr 18 | Pólya's Theory of Counting
Permutation Groups
Burnside Lemma | CGT 2.7-2.7.2 | HW 10 due
2.7.1: 1,2,4,5,9
2.7.2: 1,2,4 | |
|
| Thu | Apr 20 | Partitions | CGT 2.8-2.8.1 | 2.8.1: 1,2,3,5,10 |
|
| 15 | Tue | Apr 25 | Stable Marriage | CGT 2.9-2.9.1 | HW 11 due
2.9: 1,4
2.9.1: 1,3,4,8,7 | |
|
| Thu | Apr 27 | Combinatorial Geometry | CGT 2.10-2.10.1 | HW 12 due
2.10.1: 1,2,6,9 |
|
| Ex | Fri | May 05 | Final Exam12:30-2:20pm | | |
|
|
|