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: