An operator-theoretic approach to graph rigidity

图形刚性是一个跨学科的领域，旨在提供技术，通常在本质上组合，以识别离散几何结构的刚性和柔性特性。它的根源在于augustinlouis Cauchy（凸多面体的刚度）和James Clerk Maxwell（杆节点框架的刚度）的作品，由于理论和计算的进步以及令人惊讶的新应用领域的出现，它的发展在过去的几十年里蓬勃发展。研究对象可以被认为是具有旋转连接接头的刚性建筑块的组合，并且通常根据这些块和接头的性质进行分类；如。杆与节点、体与杆、板与铰、点与线、方向与长度框架。这种形式的约束系统在工程中是普遍存在的。桁架，机械连接和可展开的结构)，在性质上(例如：蛋白质和材料中的周期性和非周期性键节点结构)和技术(例如。自主多智能体系统的编队控制，传感器网络定位，机器学习，机器人和CAD软件)。近年来，线性分析和算符理论在考虑化学和材料科学中自然出现的无限晶体结构的无限小弯曲空间和相关的刚性算符以及图形刚性在等距图嵌入性中的应用方面发挥了重要作用。这个项目的目的是从这个新颖的角度发展图刚性的三个方面：首先，几何约束求解和有限维赋范空间中的等距图嵌入性；其次，将刚性单元模态（RUM）谱理论应用于周期性堵塞填料；第三，算子半群理论在变格柔度中的应用。这些课题处于基础科学和应用科学的交叉点；桥接算子理论、离散几何、组合学等广泛的应用领域。有限维赋范空间的设置为理解几何约束系统提供了一个背景，这些几何约束系统在由方向相关距离约束控制的意义上是各向异性的。第一个目标是为在有限维赋范空间中求解约束系统建立新的、算法高效的几何和组合准则，这些准则可用于推导刚性图实现的存在性和唯一性，并表征给定范数可等距实现的图。RUM理论的算子理论公式利用傅里叶分析将结晶杆节点框架的无限刚度矩阵表示为具有矩阵值符号函数的乘法算子。RUM谱由该符号的秩退化点组成，为框架提供了可计算的不变量和框架一阶灵活性的基本信息。与周期性填料的连接来自于通过在接触球体的中心之间插入杆而形成的相关晶体框架。第二个目标是为固定晶格晶体结构的刚性算子建立一个统一的RUM理论，该理论适用于球形和非球形环境，并推导出计算符号函数、晶体多项式和RUM谱的新方法。晶体框架的可变晶格模型允许周期性晶格经历仿射变形，这一特性使其能够通过单参数算子半群进行建模。最终目的是识别和表征晶体结构中新的和现有的可变晶格柔韧性形式，特别是那些具有形变特性的形式，并在相关的刚性算子、无穷小挠性空间和无穷小发生器之间建立联系。

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.