Lovasz proved a nonlinear identity relating the 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.
Citation
Research Report, October 2010
Article
View Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs