Séminaire OrléansGraph realisation, semidefinite programming, and universal rigidity
Louis Theran (St Andrews & MAPMO)
Thursday 04 May 2017 14:00 - Orléans - Salle de Séminaire
The graph realisation problem in d-dimensions asks for the recovery of a set P of n points in R^d from the pairwise distances corresponding to the edges of a graph G. In general this is a computationally difficult (NP-hard) problem, due to the dimension constraint. A well-known heuristic is to study a convex relaxation (an SDP feasibility problem) that can be solved efficiently. I’ll talk about which graphs G have the property that, when the point set P is chosen randomly, the SDP relaxation has a positive probability of working. This turns out to be connected to questions about bar-joint frameworks, which are mechanical structures made of rigid bars connected by freely rotating joints. This is joint work with Bob Connelly and Shlomo Gortler.