MATH 5920 Graph Theory
Course Schedule
8/17 - 8/21: Introduction -- basics of graph theory and counting
8/24-8/28: bipartite graphs, trees, planar graphs, proper colorings.
8/31-9/4: 5 color theorem, introduction to extremal graph theory, 5 proof of Mantel's theorem, Turan's theorem
9/9-9/11: Erdos-Stone-Simonovits theorem, introduction to bipartite Turan problems, projective planes, Kovari-Sos-Turan theorem
9/14-9/18: sets with distinct pairs of products, bases for the set of the first n squares, the first moment method
9/21-9/25: Constructions of graphs with no 4-cycles: Sidon sets and projective planes
9/28 - 10/2: hypergraphs, Berge cycles, Ramsey numbers
10/7-10/9: Spectral graph theory introduction
10/12-10/16: Spectral graph theory first theorems
10/19-10/23: Strongly regular graphs
10/26-10/30: the Graham-Pollak theorem, oddtown, the expander mixing lemma
Homework
Problem set 1 : Due Friday August 28
Problem set 2: Due Friday September 4
Problem set 3: Due Friday September 11
Problem set 4: Due Friday September 18
Problem set 5: Due Friday September 25
Problem set 6: Due Friday October 9
Problem set 7 : Due Friday October 23
Resources
Lecture notes: here (updated October 14)
Syllabus: here
Using LaTeX: If you do not know how to use LaTeX, you can learn how using this excellent guide that was written by Kristin Heysse. The template that is referenced in the document is here and can be copy/pasted into a new Overleaf document (or a .tex file if you have TeX set up on your own machine).
Textbooks:
Applied Combinatorics by Keller and Trotter
A walk through combinatorics by Bona
Graph Theory by Bondy and Murty
Invitation to Discrete Mathematics by Matousek and Nesetril