An operator-theoretic approach to graph rigidity

Graph rigidity is an interdisciplinary field which aims to provide techniques, often combinatorial in nature, for identifying rigidity and flexibility properties of discrete geometric structures. Its roots lie in works of Augustin-Louis Cauchy (rigidity of convex polyhedra) and James Clerk Maxwell (rigidity of bar-joint frameworks) and its development has flourished over the past several decades due to both theoretical and computational advances as well as the emergence of surprising new application areas. The objects of study can be thought of as an assembly of rigid building blocks with rotational connecting joints and are generally categorized by the nature of these blocks and joints; eg. bar-and-joint, body-and-bar, plate-and-hinge, point-and-line and direction-and-length frameworks. Constraint systems of these forms are ubiquitous in engineering (eg. trusses, mechanical linkages and deployable structures), in nature (eg. periodic and aperiodic bond-node structures in proteins and materials) and in technology (eg. formation control for autonomous multi-agent systems, sensor network localization, machine learning, robotics and CAD software).

Very recently, the role of linear analysis and operator theory has come to the fore in considering the infinitesimal flex spaces and associated rigidity operators of infinite crystallographic structures, which arise naturally in chemistry and materials science, and applications of graph rigidity to isometric graph embeddability. The aim of this project is to develop three aspects of graph rigidity from this novel perspective: firstly, geometric constraint solving and isometric graph embeddability in finite dimensional normed spaces; secondly, the application of Rigid Unit Mode (RUM) spectral theory to periodic jammed packings; and thirdly, the application of operator semigroup theory to variable lattice flexibility. These topics lie at the interface of fundamental and applied science; bridging operator theory, discrete geometry, combinatorics and a broad spectrum of application areas.

The setting of a finite dimensional normed space presents a context for understanding geometric constraint systems which are anisotropic in the sense of being governed by directionally dependent distance constraints. The first objective is to establish new, algorithmically efficient, geometric and combinatorial criteria for constraint system solving in finite dimensional normed spaces which can be used to deduce the existence and uniqueness of rigid graph realizations and to characterise graphs which are isometrically d-realisable for a given norm. The operator-theoretic formulation of RUM theory draws on Fourier analysis to represent the infinite rigidity matrix for a crystallographic bar-joint framework as a multiplication operator with matrix-valued symbol function. The RUM spectrum, which consists of points of rank degeneracy for this symbol, provides computable invariants for the framework and fundamental information on the framework's first-order flexibility. The connection to periodic packings comes from the associated crystallographic frameworks formed by inserting bars between the centres of touching spheres. The second goal is to develop a unified RUM theory for the rigidity operators of fixed lattice crystallographic structures which is applicable in both spherical and non-spherical contexts, and to derive new methods for computing symbol functions, crystal polynomials and RUM spectra. The variable lattice model for crystal frameworks allows the periodicity lattice to undergo an affine deformation, a property which lends itself to modelling through one-parameter operator semigroups. The final aim is to identify and characterise new and existing forms of variable lattice flexibility in crystallographic structures, particularly those with auxetic properties, and to establish connections between associated rigidity operators, infinitesimal flex spaces and infinitesimal generators.

Graph rigidity uses geometric and combinatorial techniques to analyse systems of constraints where there is both an underlying graph structure and accompanying geometric data. For example, take a framework composed of rigid bars and rotational joints; is this system rigid or flexible? Or consider the chemical bonds between atoms in a crystalline material; what are the mechanical properties of this system? Or consider a wireless sensor network with limited communication between nodes; does this system have a unique configuration? Or consider a convoy of autonomous vehicles; will this system maintain its formation? From structural and control engineering to materials science, molecular biochemistry and data networking, graph rigidity has contributed technological advances in diverse fields with significant societal impact. This research addresses fundamental mathematical challenges in graph rigidity which underlie many of these fields and ensures viable impact pathways by cutting across disciplinary boundaries and working with scientists in key application areas.

While the flexibility of a finite system of constraints can be understood in terms of a finite "rigidity matrix" and using linear algebra, a crystallographic structure gives rise to an infinite matrix and this is best understood from the perspective of operator theory. Rigidity analysis for infinite bar-joint frameworks is a new field which is motivated by the bond-node structures found in crystalline materials (such as zeolites and perovskites) and presents new theoretical and computational challenges. To address these fundamental challenges, this research develops the mathematical foundations of graph rigidity from the perspective of operator theory, providing new computational tools for the rigidity analysis of geometric constraint systems while also expanding the range of constraint systems to which techniques from graph rigidity can be applied. The beneficiaries of this research are wide ranging due to the interdisciplinary nature of the research and diversity of its applications. In particular, users of graph rigidity in neighbouring academic disciplines, particularly materials science, theoretical and computational chemistry, structural engineering and computer science, and in industry, particularly computer-aided design and sensor network localisation, are likely to benefit from the introduction of new mathematical methods which enrich and advance the subject. For example, in the last 30 years, advances in graph rigidity have lead to the development of efficient algorithms and computational software packages currently used for rigidity analysis in computational chemistry and protein analysis, and as component parts for geometric constraint solvers used in computer-aided design. Graph rigidity also provides a theoretical foundation for challenging problems in network localisation and in the design of metamaterials, and so theoretical advances in graph rigidity can directly benefit the technology sector and create economic impact.

The development of graph rigidity has, since its origins, been motivated by both pure mathematical questions and applied problems and this cross-pollution has been instrumental in creating impact. This research is similarly motivated and its results will be communicated to neighbouring communities in academia and industry through interdisciplinary meetings, research visits, journal publications and collaborations with key representatives. The research programme includes the training of a researcher and a PhD student and a commitment to impact the wider public, and particularly aspiring scientists, through public events, talks and masterclasses.