The graph rigidity problem in arbitrary dimension

图刚性是一个跨学科的领域，旨在提供识别离散几何结构的刚性和柔性属性的技术。这些结构可以被认为是具有连接接头的刚性建筑砌块的组件，并且通常根据这些砌块和接头的性质进行分类;例如，杆和接头、主体和杆以及面板和铰链框架。这些形式的约束系统在自然界（例如蛋白质中的周期性结构、病毒衣壳中的对称性和材料分析）、工程（例如张拉、桁架、连杆和可展开结构）和技术（例如多智能体系统的形成控制、传感器网络定位、机器学习和CAD）中普遍存在。三角形是刚性的：它的角由边长决定。正方形是灵活的：您可以将其变形为菱形，而无需更改其边缘的长度。一般来说，给定一个结构和一个在结构的底层图上建模的约束系统，区域的定义问题是：结构是否唯一（全局刚性）;是否有有限数量的实现满足给定的约束（刚性）;或者是否有无限多的实现（柔性）。图形刚性可以追溯到18世纪世纪，柯西和欧拉的理论认为，三角形结构，如测地线圆顶，其刚性杆在其端点处通过万向接头连接在一起，是固有刚性的。虽然柯西在凸的情况下得到了证明，但随后的工作继续扩展他的定理，直到康奈利在20世纪70年代证明了柔性多面体的存在。图形刚性的组合焦点可以追溯到詹姆斯·克拉克麦克斯韦，他在1864年提出了杆连接结构是刚性的基本图形的必要计数条件。一般来说，确定一个结构何时是刚性的是NP-难的，即它属于一个被广泛认为没有有效解决方案的问题族。然而，一般地（在代数几何的意义下），刚性和全局刚性可以表示为线性代数性质（分别在一个蚕豆矩阵和一个加权拉普拉斯矩阵上），然后通过交织拟阵和稀疏图理论与几何技术来攻击。拟阵是由惠特尼在20世纪30年代引入的一种数学结构。它们扩展了一组向量的线性独立性的概念，并在运筹学和组合优化中有许多重要的应用。1920年，Polaczek-Geiringer证明了麦克斯韦的条件足以表征2维一般刚性，至关重要的是，这很快就导致了用于刚性测试的快速确定性图方向算法。然而，在更高的维度麦克斯韦的条件是不够的，d维图形刚性问题（找到这样一个特性，并显示由此产生的快速算法）仍然是一个重要的开放问题，广泛的潜在application.The项目的主要目的是部署一种新的方法，以解决图形刚性问题。该项目将扩展拟阵理论的基础成果，并利用复杂的稀疏图技术。这些工具，然后将被利用一起最近加强了一个经典的维度跳跃原理从射影几何。该技术应导致开创性的组合描述时，一个通用的酒吧关节结构是刚性或柔性。然后，它将是至关重要的，在未来的大型项目中，调查的描述可以测试的快速确定性算法的程度。考虑到广泛的应用，将算法与ProFlex和KINARI等现有软件包一起实施也至关重要。

Graph rigidity is an interdisciplinary field which aims to provide techniques for identifying rigidity and flexibility properties of discrete geometric structures. The structures may be thought of as assemblies of rigid building blocks with connecting joints and are generally categorised by the nature of these blocks and joints; e.g. bar-and-joint, body-and-bar and panel and-hinge frameworks. Constraint systems of these forms are ubiquitous in nature (e.g. periodic structures in proteins, symmetry in virus capsids and the analysis of materials), in engineering (e.g. tensegrities, trusses, linkages and deployable structures) and in technology (e.g. formation control for multi-agent systems, sensor network localisation, machine learning and CAD).As a simple example, consider a triangle and a square. A triangle is rigid: its angles are determined by the lengths of its edges. A square is flexible: you can deform it into a diamond-shape without changing the lengths of its edges. In general, given a structure and a constraint system modelled on the underling graph of the structure, the defining questions of the area are whether: the structure is unique (global rigidity); there are a finite number of realisations satisfying the given constraints (rigidity); or there are infinitely many realisations (flexibility). Graph rigidity may be traced back to the 18th century and the conjectures of Cauchy and Euler that triangulated structures, such as geodesic domes, which have rigid bars connected together at their endpoints by universal joints, are inherently rigid. While Cauchy obtained a proof in the convex case, subsequent work extending his theorem continued until Connelly demonstrated the existence of flexible polyhedra in the 1970s.The combinatorial focus of graph rigidity can be traced to James Clerk Maxwell who, in 1864, developed necessary counting conditions on the underlying graph for bar-joint structures to be rigid. In general determining when a structure is rigid is NP-hard, i.e. it belongs to a family of problems for which it is widely believed there is no efficient solution. However, generically (in the sense of algebraic geometry), rigidity and global rigidity can be expressed as linear algebraic properties (on a Jacobean matrix and a weighted Laplacian matrix respectively), and then attacked by interweaving the theory of matroids and sparse graphs with geometric techniques. Matroids were introduced as a mathematical structure by Whitney in the 1930s. They extend the notion of linear independence of a set of vectors and have numerous important applications in Operational Research and Combinatorial Optimisation.In 1920 Polaczek-Geiringer proved that Maxwell's conditions are sufficient to characterise 2-dimensional generic rigidity and crucially this leads quickly to fast deterministic graph orientation algorithms for rigidity testing. However in higher dimensions Maxwell's conditions do not suffice and the d-dimensional graph rigidity problem (finding such a characterisation and showing a resulting fast algorithm) remains a crucial open problem of wide potential applicability.The main aim of the project is to deploy a novel approach in order to resolve the graph rigidity problem. The project will extend foundational results in matroid theory and utilise intricate sparse graph techniques. These tools will then be exploited alongside a very recent strengthening of a classical dimension hopping principle from projective geometry. The techniques should result in ground-breaking combinatorial descriptions of when a generic bar-joint structure is rigid or flexible. It will then be of fundamental importance, in a future large project, to investigate the extent to which the descriptions can be tested by fast deterministic algorithms. Given the wide ranging applications, it will also be crucial to implement the algorithms alongside existing software packages such as ProFlex and KINARI.