3 ms·

John Urschel's Favorite Theorem

64 points by mgdo 8y ago

gjm11 8y ago
John Urschel is a mathematician who recently retired from being an NFL American football player, at least in part because of the dangers of brain damage from repeated concussions. There have been several HN posts about him, but the only one I can find with a lot of comments is this one: https://news.ycombinator.com/item?id=14866573 https://news.ycombinator.com/item?id=14866573 His favourite theorem is described here https://arxiv.org/abs/0808.0163 https://arxiv.org/abs/0808.0163. It's a theorem in graph theory, and it says that if you have any graph, you can find a subgraph with "not too many edges" that is "like" the original graph, in a specific sense. "Not too many" means that for some value d which you get to choose, the number of edges is no more than about d times the number of vertices. (In general, the number of edges in a graph can scale like the number of vertices squared.) "Like the original graph" means that a thing called the "graph Laplacian" of the cut-down graph is a good approximation to the graph Laplacian of the original. Here's one way to think about what the graph Laplacian is. Imagine a sort of "heat flow" process on the graph, where at any given time each vertex has a temperature, and at each time step you move each vertex's temperature towards the average of its neighbours' temperatures. All the possible temperature assignments constitute a finite-dimensional vector space; call it V; the graph Laplacian is a linear map from V to itself that maps a temperature assignment to the resulting change produced by one step of the heat-flow process. It's a sort of discrete version of the second derivative operator. And it turns out that lots of interesting properties of a graph can be computed just from knowing the graph Laplacian, or even just from knowing its eigenvalues. "Good approximation" means that the relative error is on the order of 1/sqrt(d) where d is that value you got to choose earlier. So the more edges you're allowed to keep, the better the approximation can be made. (All of the above is a handwavy approximation. If you understood everything I said and want the correct version, you can find it in the paper itself.)

64 points by mgdo 8y ago

John Urschel is a mathematician who recently retired from being an NFL American football player, at least in part because of the dangers of brain damage from repeated concussions. There have been several HN posts about him, but the only one I can find with a lot of comments is this one: https://news.ycombinator.com/item?id=14866573 https://news.ycombinator.com/item?id=14866573 His favourite theorem is described here https://arxiv.org/abs/0808.0163 https://arxiv.org/abs/0808.0163. It's a theorem in graph theory, and it says that if you have any graph, you can find a subgraph with "not too many edges" that is "like" the original graph, in a specific sense. "Not too many" means that for some value d which you get to choose, the number of edges is no more than about d times the number of vertices. (In general, the number of edges in a graph can scale like the number of vertices squared.) "Like the original graph" means that a thing called the "graph Laplacian" of the cut-down graph is a good approximation to the graph Laplacian of the original. Here's one way to think about what the graph Laplacian is. Imagine a sort of "heat flow" process on the graph, where at any given time each vertex has a temperature, and at each time step you move each vertex's temperature towards the average of its neighbours' temperatures. All the possible temperature assignments constitute a finite-dimensional vector space; call it V; the graph Laplacian is a linear map from V to itself that maps a temperature assignment to the resulting change produced by one step of the heat-flow process. It's a sort of discrete version of the second derivative operator. And it turns out that lots of interesting properties of a graph can be computed just from knowing the graph Laplacian, or even just from knowing its eigenvalues. "Good approximation" means that the relative error is on the order of 1/sqrt(d) where d is that value you got to choose earlier. So the more edges you're allowed to keep, the better the approximation can be made. (All of the above is a handwavy approximation. If you understood everything I said and want the correct version, you can find it in the paper itself.)