Georgia Institute of Technology College of Sciences

A well known result in graph theory states that a graph is
connected if and only if the second eigenvalue of its Laplacian matrix
is positive. In fact, the larger the second eigenvalue, the more
connected the graph is. By varying the weights on edges, one can
in general increase the second eigenvalue which in turn affects many graph
properties such as expansion, mixing times of random walks etc.

In this talk, I will introduce conformally rigid graphs, which are
those unweighted undirected graphs in which one cannot increase the
second eigenvalue or decrease the largest eigenvalue by changing
weights. This notion turns out to be deeply connected to graph
embeddings, semidefinite programming and other ideas in geometry,
optimization and combinatorics.

Joint work with Joao Gouveia and Stefan Steinerberger