Lectures related to Introduction to Graph Theory

Markov Chains: Applications and Analysis

Explores Markov chains, focusing on the coloring problem and algorithm analysis.

Convergence of Random Walks

Explores the convergence of random walks on graphs and the properties of weighted adjacency matrices.

Cheeger's Inequalities

Explores Cheeger's inequalities for random walks on graphs and their implications.

Sparsest Cut and Concurrent Flow

Covers sparsest cut, NP-completeness, Bougains Theorem, and concurrent flow in graphs.

Shortest Paths: Negative Weights & Applications

Covers Minimum Spanning Trees, Kruskal's Algorithm, and Shortest Paths in directed graphs.

Networked Control Systems: Coordination Among Agents

Explores coordination among agents in networked control systems through graph theory and real-world examples.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Sparsest Cut: ARV Theorem

Covers the proof of the Bourgain's ARV Theorem, focusing on the finite set of points in a semi-metric space and the application of the ARV algorithm to find the sparsest cut in a graph.