\ Graph Theory

CMSC 275
Graph Theory


Instructor: Caroline J. Klivans
office: Eckhart 308A
e-mail: cjk (at) math.uchicago.edu
office hours: Monday 3-4 and by appointment
TA: Tatiana Orlova
Office Hours: Tuesday 5-6, Ryerson 178 and by appointment
Lecture: MWF 10:30-11:20 Ryerson 276

Course Description: This course covers a variety of topics from graph theory. Possible topics include: shortest paths, spanning trees, counting techniques, matchings, Hamiltonian cycles, chromatic number, extremal graph theory, probabilistic method, planarity, spectral theory, the max-flow/min-cut theorem, Ramsey theory, tournaments.

Required texts:
There is no required text for this course.
The text Discrete Mathematics and it's Applications by Rosen (the required book for Discrete Math 271) contains two chapters on graph theory, Chapters 9 and 10. Multiple copies will be on reserve in the math library.
The book Graph Theory with Applications by Bondy and Murty is available for free from Bondy's website: Bondy
When and if we get to spectral graph theory, the first few chapters of The book Spectral Graph theory by Fan chung are avaliable from her website: Chung
Notes on Threshold Graphs. Theorem 1.2.4 gives 8 definitions of threshold graphs. In class, I stated numbers 8 and 4. Where the text says dominating vertex, replace star vertex.
Threshold
Homework:
There will be weekly homework assignments. You are encouraged to work together but all students must independently write up their solutions. All homeworks are due at the beginning of class unless otherwise noted.

Hm1 Due April 6th
Hm2 Due April 13th
Hm3 Due April 20th
Solution to number 1.
Hm4 Due April 27th
Hm5 Due May 4th
Hm6 Due May 18th
Hm7 Due May 25th
Hm8 Due June 1st
(The homework has the wrong number and date!)
Schedule
Week 1: Overview of course, basic definitions (simple graph, degrees, isomorphisms) and classes of graphs (complete, bipartite, paths, cycles), Eulerian and Hamiltonian cycles.
Week 2: Trees. Definition and many equivalent characterizations, Cayley's theorem and Prufer codes, contraction deletion recurrence for couting spanning trees.
Week 3: Spectral graph theory. Adjacency, incidence, and Laplacian matrices, Matrix-Tree theorem, threshold graphs.
Week 4: (Monday) Guest lecture on the graph isomorphism problem. (Wednesday) No class. (Friday) Vertex connectivity.
Week 5: Edge connectivity, Mengers theorem, matchings
Week 6: Matchings, Hall's theorem, vertex cover, edge cover. Friday: midterm
Midterm Friday May 6th.
Week 7: Planarity, Euler's formula, Kuratowski's theorem (no proof), surface embeddings.
Week 8: Coloring, 6,5,4-color theorems. Chromatic polynomial.
Week 9: Ramsey theory and extremal graph thoery.
Week 10 (Monday) Memorial Day. (Wednesday) Final.
Final Exam:
In class Wednesday June 1st.