Graph Theory
640:428, Fall 2019
Course Info
Instructor: Swastik Kopparty (swastik.kopparty@gmail.com)
Class Time and Place: Tuesdays and Thursdays 1:40 pm - 3:00 pm, in Hill 009
Office Hours: Thursdays 3pm-4pm in Hill 432
Prerequisites: CALC3 and 640:250 (linear algebra)
References: Chartrand & Zhang (A first course in graph theory)
Syllabus
This course will be an introduction to graph theory.
Topics will include:
- Trees
- Connectivity
- Eulerian tours
- Matchings, flows and cuts
- Coloring
- Extremal graph theory
- Ramsey Theory
- Random walks
- Applications to other areas of mathematics and theoretical computer science
There will be weekly problem sets.
Grading: Homework (30%), Midterm (30%), Final (35%), Participation (5%)
Homework
HW 0, Due Wednesday September 4: Send an email to swastik.kopparty@gmail.com with subject "MATH428 HW 0" with:
(a) name, (b) major, (c) year, (d) related courses you have taken (e) anything in particular you're hoping to learn about in this course.
HW 1, Due Thursday September 12, solutions
HW 2, Due Tuesday, October 1, solutions
HW 3, Due Tuesday, October 15
HW 4, Due Thursday, November 7
HW 5, Due Tuesday, December 10, solutions
Lecture Schedule
- September 3: introduction, basic terminology
- September 5: isopmorphism, connectedness, acyclicity
- September 10: trees
- September 12: bipartite graphs
- September 17: Eulerian tours
- September 19: Hamiltonian cycles
- September 24: degree sequences
- September 26: planar graphs
- October 1: coloring planar graphs
- October 3: vertex coloring and edge coloring
- October 8: Ramsey's theorem
- October 10: Erdos's theorem on Ramsey numbers
- October 15: miscellaneous
- October 17: MIDTERM - IN CLASS
- October 22: midterm analysis, introduction to matchings
- October 24: matchings, Hall's marriage theorem
- October 29: MAGIC TRICK, augmenting paths, algorithms to find matchings
- October 31: analysis of the augmenting paths algorithm
- November 5: finding perfect matchings using the determinant of a matrix
- November 7: stable marriages
- November 12: flows, cuts
- November 14: proof of the max-flow min-cut theorem
- November 19: Menger's theorem
- November 21: k-connectivity
- November 26: THERE IS CLASS (despite day change) adjacency matrices, random walks
- November 28: NO CLASS (Thanksgiving)
- December 3: eigenvalues of the adjacency matrix, more random walks
- December 5: de Bruijn graphs, review
- December 10: review
- December 16: FINAL EXAM - 8AM-11AM, in the usual classroom (Hill 009)