Graph Theory
Spring 2024
EN.553.472/672 at Johns Hopkins: trees, matchings, network flows, spectral graph theory and the probabilistic method.
Syllabus
(JHU public syllabus)
Textbook: Douglas B. West, Introduction to Graph Theory, 2nd edition. Optional: J. A. Bondy and U. S. R. Murty, Graph Theory; Reinhard Diestel, Graph Theory, 4th edition.
Final projects
guidelines, topic suggestions and the projects presented
Weekly schedule
Section numbers refer to West. The schedule was tentative and updated during the semester.
| Week | Sections | Topics |
|---|---|---|
| 1 | 1.1, 1.2 | Applications, graphs, subgraphs, neighbors, adjacency, simple and complete graphs, bipartite graphs; \(P_n\), \(C_n\), bicliques, complements, cliques, independent sets, connectivity, adjacency and incidence matrices, degree, isomorphisms, decompositions, the Petersen graph; walks, trails, paths, cycles |
| 2 | 1.2, 1.3 | Induction, paths, cut edges and cycles; the extremal principle, bipartite graphs and odd cycles; Eulerian graphs, the degree-sum formula, bipartite subgraphs with at least half the edges |
| 3 | 1.3, 1.4, 2.1 | Sperner’s lemma; 6-cycles in the Petersen graph, edge bounds for triangle-free graphs; every tournament has a king, every tree has at least two leaves |
| 4 | 2 | Characterizations of trees, Prüfer codes and their correctness; Kruskal’s algorithm and its correctness, Dijkstra’s algorithm |
| 5 | 3 | Matchings, Hall’s theorem, integer programming formulations; matchings in \(k\)-regular bipartite graphs, dual linear programs; König’s theorem for maximum matchings and minimum vertex covers |
| 6 | 3 | König’s theorem for maximum independent sets and minimum edge covers; stable matchings and the Gale-Shapley algorithm; network flows |
| 7 | 4.3 | The Ford-Fulkerson algorithm, termination and correctness; Hall’s theorem via network flows; review of linear algebra |
| 8 | Spectra of bipartite graphs (notes, notebook); Perron-Frobenius (notebook); eigenvalue interlacing and bounds on the chromatic number (notes) | |
| Spring break | ||
| 9 | The graph Laplacian; Kirchhoff’s matrix tree theorem | |
| 10 | Normalized adjacency and Laplacian matrices; Cheeger’s inequality; spectral partitioning | |
| 11 | Ramsey numbers; the probabilistic method (Alon and Spencer, The Probabilistic Method, Chapter 1); linearity of expectation | |
| 12 | The probabilistic method; planar graphs | |
| 13 | Final project presentations |
The lecture notes linked above for weeks 8 to 10 are from Cornell’s ORIE 6334, Spectral Graph Theory, by David P. Williamson. The Jupyter notebooks are my own.