Combinatorial rigidity, symmetric geometric constraint systems, and applications

刚性的数学理论研究的是由一组刚性物体（点、线等）上的几何约束（固定长度、固定方向等）所定义的结构的刚性和柔性。一个有代表性且研究得很好的例子是杆节点框架，它是由转动节点连接的刚性杆组成的结构的数学抽象。这样的框架被称为刚性，如果它不能连续变形成另一个不一致的框架。刚性理论有着丰富的历史，可以追溯到欧拉和柯西对刚性和柔性多面体的研究。其他早期工作包括j.c.麦克斯韦对稳定和可变形结构的分析。拉曼（G. Laman）在1864年Maxwell的观察基础上，于1970年建立了二维一般布置杆节点框架为刚性的简单的充分必要计数条件，从而开创了组合刚性领域。虽然这一结果还没有推广到高维杆节点框架，但对于特殊类别的体-杆、体-铰和分子框架，已经有了显著的部分结果。拉曼具有里程碑意义的结果从1970年以来,组合和几何刚度理论的兴趣也迅速增长,和广泛的增长导致识别结果和技术领域的离散几何的主要分支之一。激发人们对刚性理论的兴趣的一个重要因素是，在科学、工程和设计领域的实际应用数量迅速增长，在这些领域，框架可以作为人工结构（如机械连杆、机器人、传感器网络、CAD软件）和自然界结构（如蛋白质和晶体）的合适数学模型。虽然以前在刚性理论中的许多工作都集中在一般框架配置和有限结构上，但具有对称和无限框架的框架在过去几年中受到了越来越多的关注。最近的工作利用表征理论的方法得到了对称框架具有最小无穷小刚性的新必要条件。然而，确定一个具有一般模和某些给定对称约束的框架具有无穷小刚性的充分条件更具挑战性，并且需要从组合学和矩阵理论中获得额外的方法。基于最近的发展，该项目旨在获得各种对称几何约束系统的无穷小刚度的新组合特征，从平面上的杆连接框架到高维的体铰或分子结构，再到CAD中出现的混合约束系统。这将导致群标记商图上的新型刚性拟阵，其描述和分析将需要各种组合和代数工具。在一般赋范线性空间的新背景下对这些问题的研究也将引入泛函分析的方法。对于欧几里得对称杆节点框架，本工作还旨在为更强的刚度概念（如全局或普遍刚度）获得新的充分必要条件。关于结果的实际应用，该项目旨在设计用于对称蛋白质刚性分析的新算法，该算法可以作为附加组件实现到刚度预测软件套件（如ProFlex或Kinari）中，以获得更准确的预测，以及开发用于控制多机器人编队的新架构和更快的算法。最后，该项目试图将对称刚性方法和功能分析观点结合起来，分析晶体学框架的刚性单元模式（RUM）谱和准晶体学框架的柔性分析。

The mathematical theory of rigidity investigates the rigidity and flexibility of structures which are defined by geometric constraints (fixed lengths, fixed directions, etc.) on a set of rigid objects (points, lines, etc.). A representative and well-studied example is the bar-joint framework which is the mathematical abstraction of a structure made of stiff bars connected by rotational joints. Such a framework is called rigid if it cannot be deformed continuously into another non-congruent framework.Rigidity theory has a rich history which can be traced back to the work of L. Euler and A. Cauchy on rigid and flexible polyhedra. Other early work includes J. C. Maxwell's analyses of stable and deformable structures. Building on an observation by Maxwell from 1864, G. Laman established simple necessary and sufficient counting conditions for a 2-dimensional generically placed bar-joint framework to be rigid in 1970, thereby launching the field of combinatorial rigidity. Although extensions of this result to higher dimensional bar-joint frameworks have not yet been found, there exist significant partial results for the special classes of body-bar, body-hinge, and molecular frameworks. Since Laman's landmark result from 1970, interest in combinatorial and geometric rigidity theory has increased rapidly, and the extensive growth in results and techniques have led to the recognition of the field as one of the main branches of discrete geometry. An important contributing factor in the spurred interest in rigidity theory is the rapidly growing number of practical applications in science, engineering, and design, where frameworks serve as suitable mathematical models for both man-made structures (e.g. mechanical linkages, robots, sensor networks, CAD software) and structures found in nature (e.g. proteins and crystals).While much previous work in rigidity theory has focused on generic framework configurations and finite structures, frameworks with symmetries and infinite frameworks have seen an ever-increasing attention over the last few years. Recent work has used methods from representation theory to obtain new necessary conditions for symmetric frameworks to be minimally infinitesimally rigid. However, determining sufficient conditions for a framework which is generic modulo some given symmetry constraints to be infinitesimally rigid is more challenging and requires additional methods from combinatorics and matroid theory. Building on recent developments, this project aims to obtain new combinatorial characterisations for the infinitesimal rigidity of diverse symmetric geometric constraint systems ranging from bar-joint frameworks in the plane through body-hinge or molecular structures in higher dimensions to hybrid constraint systems appearing in CAD. This will lead to new types of rigidity matroids on group-labeled quotient graphs whose descriptions and analyses will require a variety of combinatorial and algebraic tools. Investigations of these questions in the novel context of a general normed linear space will also bring in methods from functional analysis. For Euclidean symmetric bar-joint frameworks, the work also aims to obtain new necessary and sufficient conditions for stronger notions of rigidity such as global or universal rigidity. Regarding practical applications of the results, the project aims to design new algorithms for the rigidity analysis of symmetric proteins, which can be implemented as add-ons into rigidity prediction software suites such as ProFlex or Kinari for more accurate predictions, as well as to develop new architectures and faster algorithms for the control of multi-robot formations. Finally, the project seeks to combine symmetric rigidity methods and functional analysis perspectives in the analysis of the rigid unit mode (RUM) spectrum of crystallographic frameworks and the flexibility analysis of quasi-crystallographic frameworks.