An operator-theoretic approach to graph rigidity

图刚性的算子理论方法

• 批准号: EP/S00940X/1
• 负责人: Derek Kitson
• 金额: $ 15.54万
• 依托单位: Lancaster University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FS00940X%2F1
• 关键词: operator; theoretic; approach; graph; rigidity; operator; theoretic; approach; 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.

图形刚度是一个跨学科领域，旨在提供自然界中通常组合的技术，以识别离散几何结构的刚度和灵活性。它的根源在于奥古斯丁 - 路易斯·凯奇（Augustin-Louis Cauchy）（凸多面部的刚度）和詹姆斯·克莱克·麦克斯韦（James Clerk Maxwell）（酒吧框架的刚性），由于理论和计算进步以及出现令人惊讶的新应用领域的出现，它的发展在过去几十年中蓬勃发展。可以将研究对象视为具有旋转连接的刚性构建块的组装，通常按这些块和关节的性质进行分类。例如。酒吧和关节，车身和板板，板和铰链，刻度和方向和长度框架。这些形式的约束系统无处不在工程（例如桁架，机械链接和可部署结构），本质上（例如，蛋白质和材料中的周期性和周期性和上的键结构）以及技术（例如，用于自主性多主体系统的自治系统，传感器网络学习，机器学习，机器机器人，机器人和CAD）的形成控制。最近，线性分析和运算符理论的作用在考虑无限的挠性空间和相关的无限晶体结构的相关刚度算子方面已经脱颖而出，这是在化学和材料科学中自然出现的，以及图形刚度在等速图嵌入性中的应用。该项目的目的是从这个新颖的角度开发图形刚度的三个方面：首先，在有限维范围的空间中，几何约束求解和等距图的嵌入性；其次，将刚性单位模式（朗姆酒）光谱理论应用于周期性堵塞包装；第三，将操作员半群理论应用于可变晶格灵活性。这些主题在于基本和应用科学的界面；桥接操作者理论，离散的几何形状，组合和广泛的应用领域。有限维数规范空间的设置为理解几何约束系统提供了一种背景，这些系统是在方向依赖距离约束下控制的各向异性的。第一个目标是建立新的，算法有效的，几何和组合标准，用于在有限的尺寸规范空间中求解约束系统，这些空间可用于推断刚性图实现的存在和唯一性，并表征给定标准的d-realise d-realterians的图形。朗姆酒理论的运算符理论公式借鉴了傅立叶分析，以代表晶体学条形接头框架作为具有矩阵值值符号函数的乘法操作员的无限刚性矩阵。朗姆酒频谱由此符号的等级变性点组成，为框架的一阶灵活性提供了可计算的不变性和基本信息。与周期包装的连接来自通过在接触球中心之间插入条形的相关晶体框架。第二个目标是为固定晶格晶体结构的刚性运算符开发一个统一的朗姆酒理论，该理论适用于球形和非球面环境，并得出计算符号函数，晶体多项式和朗姆酒光谱的新方法。 Crystal Frameworks的可变晶格模型允许周期性晶格经历仿射变形，该属性可以通过单参数运算符半群进行建模。最终目的是识别和表征晶体学结构（尤其是具有辅助特性的晶格柔韧性）的新形式和现有形式，并在相关的刚性操作员，无穷小的挠性空间和无穷小发电机之间建立连接。