Course plan

Enclosed you find a list of topics as they are currently planned to appear in the course. This document will be updated as the course develops and is found in topics.pdf. Download topics.pdf.

Below is a firmer plan for the shorter time perspective.

Date	Topic	Extra Material, exercises
2021-08-31	Introduction. Overview of course and basic definitions. Chapter 1.
2021-09-07	Minimal spanning trees, Prim's and Kruskal's algorithm. Euler paths. Connectivity. Hamiltonian cycles. Prop. 1.4.2, 1.8.1, 10.1.1	Read about Prim's and Kruskal on wikipedia. Links to an external site. Exercises 1.1, 1.2, 1.3, 1.13, 1.14,1.20, 1.21, 1.28, 3.1-3.5, 10.1, 10.2, 10.8
2021-09-14	Basics of Complexity theory. NP-completeness, coloring a 3-colorable graph	The book of Arora and Barak Computatonal Complexity Links to an external site. is a good source. prob1.pdf Download prob1.pdf
2021-09-21	k-Connectivity. Structure of 2- and 3-connected graphs. Menger's theorem.	Exercises: 3,1, 3.2, 3.3, 3.4, 3.7, 3.9
2021-09-28	Network Flows, Ford-Fulkerson's proof of Max-Flow Min-Cut Theorem.	Exercises: 2.3 .6.1, 6.2, 6.3
2021-10-05	Matchings in bipartite and general graphs. Hall's marriage lemma.	Exercises: 2.1, 2.2, 2.5, 2.8,2.21
2021-10-12	Planarity. Euler's formula, Kuratowski's theorem. The dual of a planar graph.	Exercises:4.5, 4.7, 4.23.4.24
2021-11-02	Ramsey Number, Random Graphs	Excersices. 9.8, 9.9 9.10 (not so easy), 11.2,11.7
2021-11-09	More Random graphs, Second moments methods	Some useful notes from the course in 2019.Random.Graphs[2019]-ALEXANDERSSON.pdf Download Random.Graphs[2019]-ALEXANDERSSON.pdf
2021-11-16	Vertex colorability
2021-11-23	Vizing's theorem, Turan's theorem
2021-11-30	Szermeredi's regularity lemma, Erdös-Stone Theorem
2021-12-07	Expander Graphs	some notes: expander.pdf Download expander.pdf
2021-12-14	Cayley Graphs	some notes: cayley_notes.pdf Download cayley_notes.pdf Further reading: Godsil, Royle: Algebraic Graph Theory, Links to an external site. in particular Chapter 3.