AMS-MAA Joint Lecture Series 1992; 60 minutes; DVD ISBN-10: 0-8218-4408-3 ISBN-13: 978-0-8218-4408-3 List Price: US$25 Order Code: DVD/68
| "Can you hear the shape of a graph?" may sound like a nonsensical twist on the famous drum problem, but in fact it captures an intriguing analogy between manifolds and graphs. In this clear and well-paced lecture, the noted graph theorist Fan Chung exploits this analogy to produce some interesting and useful results. She starts with a historical perspective on graphs, their uses in computer science, and their inherent mathematical interest. She discusses Laplacians of graphs and hypergraphs from both the homological and graph-theoretic viewpoints. The eigenvalues of the Laplacians can be related to various properties of hypergraphs and used to strengthen and imply previous graph-theoretic results. A variety of applications to extremal combinatorics and computational complexity are discussed, in addition to a number of open problems. |