University of Waterloo

Continuous Optimization Seminar

Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs

Marcel Silva
University of Waterloo

Thursday December 2, 2010
MC 5158

Abstract

We prove a simple nonlinear identity relating the Lovasz theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish min-max theorems and to translate results related to one of the graph invariants above to the other. Classical concepts in tensegrity theory allow good interpretations of the dual SDP for the problem of finding an optimal hypersphere embedding as above. We generate a spectrum of structured SDPs on which extensions of such interpretations are possible. This is joint work with Levent Tuncel.

Back