Abstract rigidity for natural stability problems

The project will cast the following four seemingly disparate problems under the common language of rigidity theory.

1. Take a triangle and a square. The triangle is rigid: its angles are determined by the lengths of its edges. The square is flexible: you can deform it into a diamond-shape without changing the lengths of its edges. How do you determine the rigidity or flexibility of more complicated structures?

2. Suppose one is given a subset of entries from a rectangular array and would like to infer the remaining values. Assuming that the array, as a matrix, has some specific low rank makes this problem tractable even when only surprisingly few entries are known. This matrix completion problem is at the heart of recommendation system algorithms used by Netflix, Amazon and others.

3. Consider genetic networks. One seeks a model potentially involving a vast number of genes, while it is only viable to extract gene expression data from a few individuals. This phenomenon occurs often in statistical applications: problems involve a large number of random variables, but only a small number of observations due to difficulty, or expense, in collecting samples of the data. This motivates the question, what is the minimum number of observations needed to guarantee the existence of the maximum likelihood estimator of the covariance matrix in a graphical model?

4. The spatial organization of the genome in the cell nucleus plays an important role for many cellular processes including DNA replication and gene regulation. This motivates the development of methods to reconstruct the 3D structure of the genome. Understanding, analysing and identifying the nature of the configurations that can occur from experimentally observed, or inferred, contact frequency information can impact on the form and function of haploid and diploid organisms.

What do these problems have in common? This project will show they can all be studied using a generalisation of the theory of graph rigidity. Graph rigidity is an interdisciplinary field which aims to provide techniques for identifying rigidity and flexibility properties of discrete geometric structures. The structures may be thought of as assemblies of rigid building blocks with connecting joints and are generally categorised by the nature of these blocks and joints; e.g. bar-and-joint, body-and-bar and panel-and-hinge frameworks. Constraint systems of these forms are ubiquitous in nature (e.g. periodic structures in proteins, symmetry in virus capsids and the analysis of materials), in engineering (e.g. tensegrities, linkages and deployable structures) and in technology (e.g. formation control for multi-agent systems, sensor network localisation and CAD).

In order to encompass all four problems, the project will develop a generalised rigidity theory for hypergraphs and then study the new families of matroids that emerge. Matroids were introduced as a mathematical structure by Whitney in the 1930s. They extend the notion of linear independence of a set of vectors and have numerous important applications in Operational Research and Combinatorial Optimisation.

In our generalised rigidity model, the defining questions are whether: the structure is unique (global rigidity); there are a finite number of realisations satisfying the given constraints (rigidity); or there are infinitely many realisations (flexibility). Determining when a given structure is (globally) rigid is NP-hard, i.e. it belongs to a family of problems for which it is widely believed there is no efficient solution. However, the project will use novel combinatorial and rigidity theoretic techniques to efficiently resolve generic cases, applicable with high probability, and especially useful when the applications are subject to noise or measurement error. These advances will allow larger structures to be analysed across the spectrum of rigidity applications.