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.
You can find Urschel on his website or Twitter. He used to write for The Players’ Tribune, and Sports Illustrated had an article about his decision to retire from the NFL last November. You can also read an interview with him in the February 2016 issue of the Notices of the American Mathematical Society. You can find more information about the mathematicians and theorems featured in this podcast, along with other delightful mathematical treats, at kpknudson.com and here at Roots of Unity. A transcript is available here. You can subscribe to and review the podcast on iTunes and other podcast delivery systems. We love to hear from our listeners, so please drop us a line at firstname.lastname@example.org. Kevin Knudson’s handle on Twitter is @niveknosdunk, and mine is @evelynjlamb. The show itself also has a Twitter feed: @myfavethm and a Facebook page. Join us next time to learn another fascinating piece of mathematics.
*This sentence was edited after publication to correct a typo. It is true that the number of vertices grows linearly with the number of vertices (just like the per capita population of any city is 1), but the interesting part is the fact that the number of edges grows linearly with the number of vertices.
Previously on My Favorite Theorem:
Episode 0: Your hosts' favorite theorems
Episode 1: Amie Wilkinson’s favorite theorem
Episode 2: Dave Richeson's favorite theorem
Episode 3: Emille Davie Lawrence's favorite theorem
Episode 4: Jordan Ellenberg's favorite theorem
Episode 5: Dusa McDuff's favorite theorem
Episode 6: Eriko Hironaka's favorite theorem
Episode 7: Henry Fowler's favorite theorem
Episode 8: Justin Curry's favorite theorem
Episode 9: Ami Radunskaya's favorite theorem
Episode 10: Mohamed Omar's favorite theorem
Episode 11: Jeanne Clelland's favorite theorem
Episode 12: Candice Price's favorite theorem
Episode 13: Patrick Honner's favorite theorem
Episode 14: Laura Taalman's favorite theorem
Episode 15: Federico Ardila's favorite theorem
Episode 16: Jayadev Athreya's favorite theorem
Episode 17: Nalini Joshi's favorite theorem