Math 8790: Graph Theory

Course Schedule

January 27: Introduction -- counting principles, first graph theory definitions and theorems

February 3: Graph theory basics -- trees, bipartite graphs.

February 10: planar graphs, graph coloring problems.

February 17: Introduction to extremal graph theory -- Mantel's and Turan's theorem, Ramsey's theorem

February 24: Erdos-Stone-Simonovits theorem, discussion of bipartite Turan numbers, Schur's theorem, Fermat's last theorem over finite fields. Introduction to Probabilistic method -- expectation and variance, first moment method, lower bounds for Turan and Ramsey numbers.

March 3: Markov and Chebyshev inequalities with applications

March 10: Chernoff bound, Lovasz Local Lemma, applications

March 17: Kovari-Sos-Turan theorem with number theory applications. Constructions of C_4-free graphs via combinatorial number theory and finite geometry

March 24: Sidon sets, algebraically defined graphs, orthogonal polarity graphs

March 31: Linear algebra preliminaries, the adjacency matrix, counting walks, structure from the eigenvalue equation, spectral Mantel's theorem

April 7: structure from the eigenvalue equation, spectral Mantel's theorem, Stanley's bound, Nosal's theorem, maximum spectral radius of F-free graphs, Moore graphs, Hoffman-Singleton theorem, strongly regular graphs

April 14: the expander mixing lemma, the Hoffman ratio bound, sum-product theorems in finite fields

April 21: the Graham-Pollak theorem, combinatorial nullstellensatz and applications

April 28: extremal set theory: oddtown, eventown, Erdos-Ko-Rado, 2-distance sets.