Matroid Elevations and Rigid Frameworks

d维（杆节点）框架是在d维欧几里德空间（d空间）中以万向节连接在一起的杆的集合。如果每个关节的连续运动保持杆的长度，保持所有关节对之间的距离，那么框架就是刚性的。在土木工程、机器人技术、蛋白质折叠和（生物）化学中的分子结构等不同领域的许多应用中，确定给定框架何时是刚性的是一个重要问题。这个问题在一维框架下很容易解决，但不太可能有一个有效的算法来解决高维问题的所有实例，因为它是已知的“np困难”，也就是说，它属于一个被普遍认为没有有效解决方案的问题族。然而，如果我们将注意力限制在关节处于一般位置的框架上，这个问题就会变得更容易处理（这给了我们一个具有给定一组杆和关节的框架的“典型”行为）。在这种情况下，刚性仅取决于框架的底层图形（其中节点由顶点表示，条形由边表示），其目的是表征那些框架在d维空间中具有一般刚性的图形。James Clerk Maxwell（1864）给出了框架在d空间中是刚性的必要条件。不难看出，当d=1时，这些条件也足以表明刚性。Polaczek-Geiringer（1927）和随后的Laman（1970）表明，当d=2时，麦克斯韦条件具有一般刚性的特征。当d= 2时，他的条件不具有一般刚性的特征，而当d=3时，找到这样的特征是离散几何中的一个中心开放问题。自2003年以来，我一直在研究这个问题和其他相关问题，最近与东京大学的凯蒂·克林奇（Katie Clinch）和谷川信一（Shin-Ichi Tanigawa）合作，取得了重大突破。我们的方法是一种分析图的d维“刚性矩阵”的新方法。拟阵是1935年由惠特尼和中泽独立提出的一种数学结构。它们扩展了向量集线性无关的概念，在运筹学，特别是组合优化中有许多重要的应用。图形的d维刚性矩阵是图形边缘上的矩阵，其中一组边缘是独立的，如果它们对图形的一般实现作为d空间中的条形关节框架的运动产生独立约束。Graver在1990年利用d空间中刚性框架的两个基本性质定义了抽象d-刚性拟阵族。他推测d维刚度矩阵是最大的抽象d刚度矩阵。当d=1,2时，他验证了他的猜想，但当d= 1,3时，他的猜想被证明是错误的。Clinch， Tanigawa和我最近使用了矩阵直立理论（由Crapo于1970年引入），通过证明“协因子矩阵”（来自近似理论的特定矩阵）是最大抽象3刚性矩阵，并描述了该矩阵的独立性，在d=3时剩余未解决的情况下取得了重大进展。本项目旨在继续这条研究路线：通过证明协因子矩阵等于三维刚度矩阵来完成d=3时Graver猜想的解；研究了d- bbbb3时最大抽象d-刚度矩阵的独立性；应用类似的技术来描述与离散几何中的其他问题相关的拟阵（例如低秩矩阵补全）；开发快速求出这些拟阵的秩函数的算法。所要求的资金用于在未来两年内对东京进行为期1个月的访问，并参加几次会议和讲习班，以传播我们的成果并获得宝贵的反馈。

A d-dimensional (bar-joint) framework is a collection of bars joined together at universal joints in d-dimensional Euclidean space (d-space). The framework is rigid if every continuous motion of the joints which preserves the lengths of the bars, preserves the distances between all pairs of joints. Deciding when a given framework is rigid is an important problem with many applications in diverse areas such as civil engineering, robotics, protein folding and molecular structure in (bio)chemistry. The problem is easily solvable for 1-dimensional frameworks but it is unlikely that there will be an efficient algorithm for solving all instances of the problem in higher dimensions since it is known to be `NP-hard' i.e. it belongs to a family of problems for which it widely believed there is no efficient solution. The problem becomes more tractable, however, if we restrict our attention to frameworks whose joints are in generic position (this gives us the `typical' behaviour of a framework with a given set of bars and joints). In this case rigidity depends only on the underlying graph of the framework (in which joints are represented by vertices and bars by edges) and the aim is to characterise those graphs whose frameworks are generically rigid in d-dimensional space. James Clerk Maxwell (1864) gave necessary conditions for a framework to be rigid in d-space. It is not difficult to see that these conditions are also sufficient to imply rigidity when d=1. Polaczek-Geiringer (1927) and subsequently Laman (1970) showed that Maxwell's conditions characterise generic rigidity when d=2. His conditions do not characterise generic rigidity when d>2 and finding such a characterisation when d=3 is a central open problem in discrete geometry. I have been working on this and other related problems since 2003 and have recently made a significant breakthrough in collaboration with Katie Clinch and Shin-Ichi Tanigawa of the University of Tokyo. Our approach is a novel way of analysing the d-dimensional `rigidity matroid' of a graph. Matroids were independently introduced as a mathematical structure by Whitney and Nakasawa in 1935. They extend the notion of linear independence of a set of vectors and have many important applications in Operational Research, particularly in Combinatorial Optimisation. The d-dimensional rigidity matroid of a graph is a matroid on the edges of the graph, in which a set of edges is independent if they give rise to independent constraints on the motion of a generic realisation of the graph as a bar-joint framework in d-space. Graver defined the family of abstract d-rigidity matroids in 1990 using two fundamental properties of rigid frameworks in d-space. He conjectured that the d-dimensional rigidity matroid is the maximal abstract d-rigidity matroid. He verified his conjecture when d=1,2 but his conjecture was subsequently shown to be false when d>3. Clinch, Tanigawa and myself recently used the theory of matroid erections (introduced by Crapo in 1970) to make significant progress on the remaining unsolved case when d=3 by showing that the `cofactor matroid', a particular matroid from approximation theory, is the maximal abstract 3-rigidity matroid and characterising independence in this matroid. This project aims to continue this line of research: to complete the solution of Graver's conjecture when d=3 by showing that the cofactor matroid is equal to the 3-dimensional rigidity matroid; to characterise independence in the maximal abstract d-rigidity matroid when d>3; to apply similar techniques to characterise matroids associated with other problems in discrete geometry (such as low rank matrix completion); to develop fast algorithms to evaluate the rank functions of these matroids. The requested funding is for four 1 month visits to Tokyo in the next two years and attendance at several conferences and workshops to disseminate our results and receive valuable feedback.