Graph Expansion and its Relationship with Probability and Geometry

Start: 12/07/2015 - 4:15pm
End  : 12/07/2015 - 5:15pm

Applied Math Seminar

Angelica Gonzalez (University of Arizona)


Thinking of a graph as a network, the expansion constant measures how efficient a graph is
with respect to optimization of cost, connectivity, and robustness. The expansion constant of a graph
measures the sparsity (in terms of the number of edges, relative to the number of vertices) while still
maintaining connectivity of a graph. In this talk we explore the notion of the expansion constant of
a graph and it's relationship to the spectrum of the adjacency matrix of a graph. This will lead to
a discussion of how some geometric and probabilistic techniques are useful in the study of expansion.
We will conclude by investigating some of these notions for a specifi c class of 3-regular graphs.

Emmy Noether Room, Millikan 1021, Pomona College