Timestamps:

00:00:00 : Introduction

00:04:30 : Being a professional mathematician and academia vs industry

00:09:41 : John's taste in mathematics

00:13:00 : Outline

00:17:23 : Braess's Paradox: "Opening a highway can increase traffic congestion."

00:25:34 : Prisoner's Dilemma. We need social forcing mechanisms to avoid undesirable outcomes (traffic jams).

00:31:20 : What is a graph

00:36:33 : Graph bottlenecks. Practical situations: Task assignment, the economy, organizational management.

00:42:44 : Quantifying bottlenecks: Cheeger's constant

00:46:43 : Cheeger's constant sample computations

00:55:48 : Graph Laplacian

00:58:30 : Graph Laplacian: Relation to Laplacian from calculus

01:00:27 : Graph Laplacian: 1-dimensional example

01:01:22 : Graph Laplacian: Analyst's Laplacian vs Geometer's Laplacian (they differ by a minus sign)

01:04:44 : Graph Laplacian: Some history

01:07:35 : Cheeger's Inequality: Statement

01:09:37 : \*\*\*Cheeger's Inequality: A great example of beautiful mathematics\*\*\*

01:10:46 : Cheeger's Inequality: Computationally tractable approximation of Cheeger's constant

01:14:57 : Rayleigh quotient, discussion of proof of Cheeger's inequality

01:19:16 : Harmonic oscillators: Springs heuristic for lambda\_2 and Cheeger's inequality

01:22:20 : Interlude: Tutte's Spring Embedding Theorem (planar embeddings in terms of springs)

01:26:23 : Harmonic oscillators: Resume lambda\_2 discussion and spring tension

01:29:45 : Interlude: Graph drawing using eigenfunctions

01:33:17 : Harmonic oscillators: Resume lambda\_2 discussion: complete graph example and bottleneck is a perturbation of two disconnected components

01:38:26 : Summary thus far and graph bisection

01:42:44 : Graph bisection: Large eigenvalues for PCA vs low eigenvalues for spectral bisection

01:43:40 : Graph bisection: 1-dimensional intuition

01:44:40 : Graph bisection: Nodal domains

01:46:29 : Graph bisection: Aha, the 1-d example now makes sense. Splitting by level set of second eigenfunction is a good way to partition domain.

01:47:43 : Spectral graph clustering (complementary to graph bisection)

01:51:50 : Ng-Jordan-Weiss paper

01:52:10 : PageRank: Google's algorithm for ranking search results

01:53:44 : PageRank: Markov chain (Markov matrix)

01:57:32 : PageRank: Stationary distribution

02:00:20 : Perron-Frobenius Theorem

02:06:10 : Spectral gap: Analogy between bottlenecks for graphs and bottlenecks for Markov chain mixing

02:07:56 : Conclusion: State of the field, Urschel's recent results

02:10:27 : Joke: Two kinds of mathematicians