On today’s episode of our podcast My Favorite Theorem, my cohost Kevin Knudson and I were excited to talk to John Urschel, who retired from his career as an offensive lineman for the Baltimore Ravens last year and is now a full-time graduate student in applied math at MIT. (Because some of our listeners/readers might find a little background helpful: the Baltimore Ravens are a team in the National Football League, also known as the NFL. They play American football, a game that is different from the football that is also known as soccer.) You can listen to the episode here or at kpknudson.com, where there is also a transcript.

After some discussion of Australian rules football (my one regret about this episode is that you can’t see the mixture of confusion and betrayal on Urschel’s face as we tried to explain Australian rules football to him), we moved on to the theorem.

Urschel chose to share a theorem about graph theory by Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. You can read their paper on the work here. In this context, a graph is a collection of nodes and edges; the people in a social network (nodes) and the connections between them (edges) form one example of this kind of graph. Sometimes the edges of a graph can be weighted, meaning you can assign a number to each edge that represents some strength or weight of a connection. To each graph one can associate an object called the graph Laplacian that encodes certain properties of the graph.

Batson, Spielman, and Srivastava’s theorem says that given a graph, perhaps with an unwieldy number of edges, one can find a new graph with many fewer edges that has almost exactly the same data encoded in the graph Laplacian. Specifically, they show that the number of edges* in these graphs (called spectral sparsifiers) grows linearly with the number of vertices. Urschel told us why he loves the theorem, which is sort of on the boundary between theoretical and applied math. Some applied mathematicians really like to dig into the equations governing biology or physics applications; others, like Urschel, prefer applied math that is a little more abstract and are not always motivated by immediate applications.

We also talked about the asymmetric traveling salesman problem, which Urschel and his advisor Michel Goemans are interested in. The traveling salesman problem is the question of finding the shortest (or fastest, cheapest, etc.) route between cities (or pubs); in the asymmetric version, the distance from point A to point B might be different from the distance from B to A. (Think one-way streets or bridges that only charge a toll in one direction.) Urschel mentioned an August 2017 paper about a new algorithm for the problem, which you can find here. The Gödel’s Lost Letter blog covered it as well.

In each episode, we ask our guest to pair their theorem with food, beverage, art, music, or other delight in life. Urschel chose Miller 64 beer. You’ll have to listen to the episode to hear why he thinks it’s the spectral sparsifier of beers.