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

  • [EC1] Enumerative Combinatorics, Volume I by R. P. Stanley. UM access.
  • [Sta] An Introduction to Hyperplane Arrangements by R. P. Stanley. Link.
  • [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 [2024-11-05 Tue]. Hints.
  5. Homework 5 due [2024-11-26 Tue]. Hints.
  6. Homework 6 due [2024-12-09 Mon].

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
  10. Finite projective planes
  11. Combinatorial geometries
  12. More on geometric lattices
  13. Generalizing independence and matroids
  14. Hyperplane arrangements
  15. Mobius functions
  16. Graphical arrangements
  17. Characteristic polynomials
  18. Combinatorics of geometric lattice Mobius functions

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 pages 1--3.5 of 10  
[2024-10-24 Thu] Finite projective planes [vLW, Chapter 23] rest of 10 Non-Desarguesian planes
[2024-10-29 Tue] Combinatorial geometries [vLW, Chapter 23] pages 1--4 of 11  
[2024-10-31 Thu] Geometric lattices [vLW, Chapter 23] pages 5--7 of 11  
[2024-11-05 Tue] More on geometric lattices and posets [Sta, Lecture 3], [EC1, 3.1+3.3] 12 Semimodular lattice wiki
[2024-11-07 Thu] Generalizing independence and matroids [Sta, Lecture 3], [vLW, Chapter 23] pages 1--3 of 13  
[2024-11-12 Tue] Hyperplane arrangements [Sta, Lecture 1] pages 1--3.5 of 14  
[2024-11-14 Thu] Characteristic polynomials [Sta, Lecture 1] rest of 14  
[2024-11-19 Tue] Mobius functions [Sta, Lectures 1+2] 15  
[2024-11-21 Thu] Graphical arrangements [Sta, Lectures 1+2] 16  
[2024-11-26 Tue] More on characteristic polynomials [Sta, Lectures 2+5] 17  
[2024-11-28 Thu] Thanksgiving Break      
[2024-12-03 Tue] Combinatorics of geometric lattice Mobius functions [Sta, Lectures 3+4] pages 1--3.5 of 18  
[2024-12-05 Thu] Broken Circuit Complex [Sta, Lecture 4] rest of 18  
Date published: Tuesday, August 27, 2024