John Urschel received his bachelors and masters in mathematics from Penn State and then went on to become a professional football player for the Baltimore Ravens in 2014. During his second season, Urschel began his graduate studies in mathematics at MIT alongside his professional football career. Urschel eventually decided to retire from pro football to pursue his real passion, the study of mathematics, and he completed his doctorate in 2021. Urschel is currently a scholar at the Institute for Advanced Study where he is actively engaged in research on graph theory, numerical analysis, and machine learning. In addition, Urschel is the author of Mind and Matter, a New York Times bestseller about his life as an athlete and mathematician, and has been named as one of Forbes 30 under 30 for being an outstanding young scientist.

In this episode, John and I discuss a hodgepodge of topics in spectral graph theory. We start off light and discuss the famous Braess's Paradox in which traffic congestion can be increased by opening a road. We then discuss the graph Laplacian to enable us to present Cheeger's Theorem, a beautiful result relating graph bottlenecks to graph eigenvalues. We then discuss various graph embedding and clustering results, and end with a discussion of the PageRank algorithm that powers Google search.

Patreon: https://www.patreon.com/timothynguyen

Originally published on June 9, 2022 on YouTube: https://youtu.be/O6k0JRpA2mg

Timestamps:

I. Introduction

• 00:00: Introduction

II. Spectral Graph Theory Basics

• 31:20: What is a graph

III. Cheeger's Inequality and Harmonic Oscillators

• 1:07:35: Cheeger's Inequality: Statement

IV. Graph bisection and clustering

• 1:38:26: Summary thus far and graph bisection

V. Markov chains and PageRank

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

Further Reading:

• A. Ng, M. Jordan, Y. Weiss. "On Spectral Clustering: Analysis and an algorithm"