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.