Matroid Elevations and Rigid Frameworks

A d-dimensional (bar-joint) framework is a collection of bars joined together at universal joints in d-dimensional Euclidean space (d-space). The framework is rigid if every continuous motion of the joints which preserves the lengths of the bars, preserves the distances between all pairs of joints. Deciding when a given framework is rigid is an important problem with many applications in diverse areas such as civil engineering, robotics, protein folding and molecular structure in (bio)chemistry.

The problem is easily solvable for 1-dimensional frameworks but it is unlikely that there will be an efficient algorithm for solving all instances of the problem in higher dimensions since it is known to be `NP-hard' i.e. it belongs to a family of problems for which it widely believed there is no efficient solution.

The problem becomes more tractable, however, if we restrict our attention to frameworks whose joints are in generic position (this gives us the `typical' behaviour of a framework with a given set of bars and joints). In this case rigidity depends only on the underlying graph of the framework (in which joints are represented by vertices and bars by edges) and the aim is to characterise those graphs whose frameworks are generically rigid in d-dimensional space.

James Clerk Maxwell (1864) gave necessary conditions for a framework to be rigid in d-space. It is not difficult to see that these conditions are also sufficient to imply rigidity when d=1. Polaczek-Geiringer (1927) and subsequently Laman (1970) showed that Maxwell's conditions characterise generic rigidity when d=2.

His conditions do not characterise generic rigidity when d>2 and finding such a characterisation when d=3 is a central open problem in discrete geometry. I have been working on this and other related problems since 2003 and have recently made a significant breakthrough in collaboration with Katie Clinch and Shin-Ichi Tanigawa of the University of Tokyo.

Our approach is a novel way of analysing the d-dimensional `rigidity matroid' of a graph. Matroids were independently introduced as a mathematical structure by Whitney and Nakasawa in 1935. They extend the notion of linear independence of a set of vectors and have many important applications in Operational Research, particularly in Combinatorial Optimisation.

The d-dimensional rigidity matroid of a graph is a matroid on the edges of the graph, in which a set of edges is independent if they give rise to independent constraints on the motion of a generic realisation of the graph as a bar-joint framework in d-space. Graver defined the family of abstract d-rigidity matroids in 1990 using two fundamental properties of rigid frameworks in d-space.

He conjectured that the d-dimensional rigidity matroid is the maximal abstract d-rigidity matroid. He verified his conjecture when d=1,2 but his conjecture was subsequently shown to be false when d>3. Clinch, Tanigawa and myself recently used the theory of matroid erections (introduced by Crapo in 1970) to make significant progress on the remaining unsolved case when d=3 by showing that the `cofactor matroid', a particular matroid from approximation theory, is the maximal abstract 3-rigidity matroid and characterising independence in this matroid.

This project aims to continue this line of research: to complete the solution of Graver's conjecture when d=3 by showing that the cofactor matroid is equal to the 3-dimensional rigidity matroid; to characterise independence in the maximal abstract d-rigidity matroid when d>3; to apply similar techniques to characterise matroids associated with other problems in discrete geometry (such as low rank matrix completion); to develop fast algorithms to evaluate the rank functions of these matroids. The requested funding is for four 1 month visits to Tokyo in the next two years and attendance at several conferences and workshops to disseminate our results and receive valuable feedback.