Expander graphs
Time and place
12:30 PM on Tuesday, April 3rd, 2012; NAC 6-113
Paul Gunnells (University of Massachusetts, Amherst)
Abstract
A graph is a mathematical object consisting of a set of points, called vertices, joined by arcs, called edges. Graphs arise in many applications, for instance in modelling networks, link structures of websites, and in the study of molecular structure in chemistry and physics.
The goal of our talk is to discuss a quantitative measure of how "efficiently connected" a given graph is, and to give examples of families of graphs that are very efficiently connected. To see what this means, think of the problem of efficient network design: if one imagines a graph to represent a computer network with the vertices being computers and the edges network connections, then one would like to maximize the flow of information through the network while minimizing the cost of building the network. There is a class of graphs, appropriately called expander graphs, that solves this problem extremely well. In our talk we will explain these concepts and give some examples of Ramanujan graphs.
