Math 565: Combinatorics and Graph Theory

This is an introductory combinatorics class at the graduate level. I plan for the first half of the class to be about graph theory, including topics such as extremal graph theory, Ramsey theory, chromatic numbers and polynomials. For the second half of the class, I plan for us to study geometric combinatorics, including topics such as projective geometries, geometric lattices, matroids, and hyperplane arrangements. However, precise topics are subject to change.

Syllabus

The syllabus is available here.

Important Dates

  • Last day to add/drop without “W”: [2024-09-16 Mon].
  • Midterm Exam: [2024-10-10 Thu] (in class).
  • Last day to withdraw from course with “W”: [2024-11-01 Fri]
  • Take Home Final Exam: Due [2024-12-17 Tue] at 12:30pm.

Office Hours

  • Monday’s 1pm–2pm (Math Lab, EH B860)
  • Tuesday’s 10am–11am (EH 3827)
  • Thursday’s 1pm–2pm (EH 3827)

Textbook

The optional textbook is A Course in Combinatorics by J. H. van Lint and R. M. Wilson, 2nd edition, Cambridge University Press, 2018. UM students can access the book electronically here.

References

  • [vLW] A Course in Combinatorics by J. H. van Lint and R. M. Wilson. UM access.

Homework Assignments

  1. Homework 1 due [2024-09-12 Thu]. Hints.
  2. Homework 2 due [2024-09-24 Tue]. Hints.
  3. Homework 3 due [2024-10-08 Tue]. Hints.
  4. Homework 4 due TBD.

Notes

  1. A quick introduction to graphs
  2. Mantel’s theorem and Turan’s theorem
  3. Ramsey’s theorem
  4. Van der Waerden’s theorem
  5. Planar graphs
  6. Graph colorings
  7. Hall’s marriage theorem
  8. Flows in networks and the max-flow min-cut theorem
  9. Latin squares

List of Lectures

Date Topics Additional Reading Class Notes Additional Materials
[2024-08-27 Tue] Intro and Mantel’s theorem [vLW, Chapters 1 and 4] 1 + pages 1--3 of 2  
[2024-08-29 Thu] Turan’s theorem [vLW, Chapter 4] + Wiki rest of 2 (except last page)  
[2024-09-03 Tue] Ramsey’s theorem [vLW, Chapter 3] + Wiki 3  
[2024-09-05 Thu] Van der Waerden’s theorem Wiki 4  
[2024-09-10 Tue] Planar graphs [vLW, Chapter 33] + Wiki first 4 pages of 5 Surfaces from polygons
[2024-09-12 Thu] Euler’s formula + graph colorings [vLW, Chapter 33] rest of 5 + first 2 pages of 6  
[2024-09-17 Tue] Acyclic orientations + five color theorem [vLW, Chapter 33] rest of 6  
[2024-09-19 Thu] Hall’s marriage theorem [vLW, Chapter 5] first 4 pages of 7  
[2024-09-24 Tue] HMT continued, Kőnig’s theorem, Birkhoff’s theorem [vLW, Chapter 5] pages 5--8 of 7  
[2024-09-26 Thu] Flows and max-flow min-cut theorem [vLw, Chapter 7] pages 1--4.3 of 8  
[2024-10-01 Tue] Circulations and Latin squares [vLW, Chapter 17] rest of 8, pages 1--3 of 9  
[2024-10-03 Thu] Latin squares (continued) + fire alarm interruption [vLW, Chapter 17] pages 3--5 of 9  
[2024-10-08 Tue] Latin squares + Dinitz conjecture [vLW, Chapter 17] pages 5--8 of 9  
[2024-10-10 Thu] Midterm (content of notes 1--8 + HWs 1--3)      
[2024-10-15 Tue] Fall break      
[2024-10-17 Thu] Dinitz conjecture continued [vLW, Chapter 17] rest of 9  
[2024-10-22 Tue] Finite projective planes Wiki    
Date published: Tuesday, August 27, 2024