Expander Graphs
July 21st, 2005 by WaltIt’s basically impossible to know all of the important concepts and results in mathematics. It’s impossible to even have heard of all of the important concepts and results in mathematics. For example, I’d never heard of expander graphs, which apparently have widespread applications in combinatorics and computer science, and even have an interpretation in terms of group representations.
Michael Nielsen has a series of posts on expander graphs beginning here. For more background, he links to lecture notes on the subject by Linial and Wigderson.
April 26th, 2006 at 9:20 pm
[...] We’ve previously linked to some expository material on expanders. [...]
October 1st, 2006 at 8:34 pm
[...] The latest issue of the Bulletin of the AMS is out. The feature article is Expander graphs and their applications by Hoory, Linial, and Wigderson. Expander graphs are a kind of graph that are important in computational complexity theory; we discussed them once before. Y.S. Sinai, a mathematician who works on topics quite close to physics, has an interesting article on the cultural differences called Mathematicians and physicists = cats and dogs?. [...]