权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

项目摘要

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.

图的刚性是一个跨学科的领域，其目的是提供技术，往往是组合的性质，用于识别刚性和柔性特性的离散几何结构。它的根源在于奥古斯丁-路易柯西（凸多面体的刚性）和詹姆斯克拉克麦克斯韦（杆关节框架的刚性）的作品，它的发展在过去几十年中蓬勃发展，由于理论和计算的进步，以及令人惊讶的新应用领域的出现。研究的对象可以被认为是一个组件的刚性积木与旋转连接关节，并通常分类的性质，这些块和关节;例如。杆-关节、体-杆、板-铰、点-线和方向-长度框架。这些形式的约束系统在工程中无处不在（例如，桁架、机械连杆和可展开结构），在自然界中（例如，蛋白质和材料中的周期性和非周期性键结结构）和技术（例如，自主多智能体系统的编队控制、传感器网络定位、机器学习、机器人技术和CAD软件）。最近，线性分析和算子理论的作用已经走到了前列，在考虑无限小的弯曲空间和相关的刚性运营商的无限晶体结构，这自然出现在化学和材料科学，以及应用程序的图形刚性等距图嵌入。这个项目的目的是从这个新的角度发展三个方面的图形刚性：第一，几何约束求解和等距图嵌入有限维赋范空间;第二，刚性单元模式（RUM）谱理论的应用定期堵塞包装;第三，应用算子半群理论可变格的灵活性。这些主题位于基础科学和应用科学的接口;桥接算子理论，离散几何，组合学和广泛的应用areas.The设置的有限维赋范空间提出了一个上下文理解的几何约束系统是各向异性的意义上的方向依赖的距离约束。第一个目标是建立新的，算法上有效的，几何和组合的标准，约束系统解决有限维赋范空间，可用于推导刚性图实现的存在性和唯一性，并在给定的范数下等距d-可实现的图。RUM理论的算子理论公式利用傅立叶分析将晶体学杆-关节框架的无限刚度矩阵表示为具有矩阵值符号函数的乘法算子。RUM频谱，它包括点的秩退化这个符号，提供了可计算的不变量的框架和基本信息的框架的一阶灵活性。与周期性堆积的联系来自于相关的晶体学框架，这些框架是通过在相互接触的球体的中心之间插入棒而形成的。第二个目标是发展一个统一的RUM理论的刚性运营商的固定晶格晶体结构，这是适用于球形和非球形的背景下，并推导出新的方法计算符号函数，晶体多项式和RUM光谱。晶体框架的可变晶格模型允许周期性晶格进行仿射变形，这一特性有助于通过单参数算子半群进行建模。最终的目标是识别和识别新的和现有的形式的可变晶格的灵活性在晶体结构，特别是那些与拉胀性质，并建立相关的刚性运营商，无穷小弯曲空间和无穷小发电机之间的连接。