Codes and Expansions (CodEx) Seminar

Stefan Steinerberger (University of Washington Seattle):
Conformally Rigid Graphs

Given a graph \(G=(V,E)\), the smallest (nonzero) eigenvalue of its Laplacian matrix is a great measure for how connected the graph is (also known as the algebraic connectivity); for example: adding edges increases it.  What if we instead shift the weights of the edges around, can we make that eigenvalue larger?  (A toy example would be: given a computer network, can we move some of the cables around to get a higher efficiency network without having to buy any new cables?).  It depends on the graph but for some graphs the answer is No. These graphs are already maximizing their algebraic connectivity, shifting weights around won't help.  These are quite interesting graphs which we call conformally rigid (and the name will be explained).  The family of conformally rigid graphs is combinatorially surprisingly rich, we don't understand it fully, and we will survey what we know (and don't know!).  Joint work with Rekha Thomas.