EPSRC Reference: 
EP/T030461/1 
Title: 
Matroid Elevations and Rigid Frameworks 
Principal Investigator: 
Jackson, Professor B 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Sch of Mathematical Sciences 
Organisation: 
Queen Mary University of London 
Scheme: 
Overseas Travel Grants (OTGS) 
Starts: 
01 September 2020 
Ends: 
28 February 2023 
Value (£): 
58,159

EPSRC Research Topic Classifications: 
Logic & Combinatorics 
Mathematical Aspects of OR 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
A ddimensional (barjoint) framework is a collection of bars joined together at universal joints in ddimensional Euclidean space (dspace). 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 1dimensional 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 `NPhard' 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 ddimensional space. James Clerk Maxwell (1864) gave necessary conditions for a framework to be rigid in dspace. It is not difficult to see that these conditions are also sufficient to imply rigidity when d=1. PolaczekGeiringer (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 ShinIchi Tanigawa of the University of Tokyo.
Our approach is a novel way of analysing the ddimensional `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 ddimensional 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 barjoint framework in dspace. Graver defined the family of abstract drigidity matroids in 1990 using two fundamental properties of rigid frameworks in dspace. He conjectured that the ddimensional rigidity matroid is the maximal abstract drigidity 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 3rigidity 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 3dimensional rigidity matroid; to characterise independence in the maximal abstract drigidity 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.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
