Intro to graph theory
I will be teaching MA 216 : Introduction to Graph theory during the Jan-April 2024 semester (at IISc, Bangalore).
Updates:
I will be updating the notes at least once a month in 2024 (latest update: 29 May 2024). I hope to make this into a short fun book, so feel free to send me feedback.
Description: This is an introductory course. The focus will be on seeing a wide variety of applications, and so will include an eclectic dose of Graph Algorithms, Algebra and Game theory. No prerequisites are expected, except for some familiarity with linear algebra (at the level of UM102).
Here is a rough list of topics:
Directed and undirected graphs, trees, connectedness, graph colouring, chromatic number, Ramsey’s theorem, probabilistic method, breadth-first search, depth-first search, topological sort, shortest paths, Dijkstra’s algorithm, search trees, hash tables.
Matrices associated with graphs. Adjacency matrix, Laplacian matrix, spectrum of a graph, page-rank algorithm; bipartite graphs, stable matchings, Conway’s topograph.
Suggested references (incomplete) :
Invitation to discrete mathematics, Matousek, Nesetril
Graph theory, Diestel
Algebraic and Spectral Graph theory, Spielman
Algorithms Illuminated, Roughgarden (a smooth playlist of the greatest hits)
Algorithm design, Kleinberg, Tardos
Benny Sudokov's Lecture notes (covers solid ground in only 80 pages)
For puzzles:
Algebraic Combinatorics, Stanley (which has a section called Mathematical gems)
33 miniatures, Matousek
Proofs from the book, Aigner, Ziegler