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年以来，我一直在研究这个问题和其他相关问题，最近与东京大学的凯蒂·克林奇和谷川信一合作，取得了重大突破。我们的方法是一种新的方式来分析的d维刚性拟阵的图。拟阵是由Whitney和Nakasawa在1935年独立引入的数学结构。它们扩展了一组向量的线性独立性的概念，在运筹学中有许多重要的应用，特别是在组合优化中。图的d维刚性拟阵是图的边上的拟阵，其中如果它们对图的一般实现的运动产生独立的约束，则它们是独立的。Graver在1990年利用d-空间中刚性框架的两个基本性质定义了抽象d-刚性拟阵族。他证明了d-维刚性拟阵是最大抽象d-刚性拟阵。他验证了他的猜想时，d= 1，2，但他的猜想随后被证明是错误的，当d>3。克林奇，谷川和我最近使用的理论拟阵勃起（介绍了Crapo在1970年）取得重大进展的剩余未解决的情况下，当d=3表明，“余因子拟阵”，一个特定的拟阵从近似理论，是最大的抽象3-刚性拟阵和特征的独立性在这个拟阵。本项目的目标是继续这一研究方向：通过证明余因子拟阵等于三维刚性拟阵，完成d=3时Graver猜想的求解;当d>3时，最大抽象d-刚性拟阵的独立性;将类似的技术应用于与离散几何中其他问题相关的拟阵（如低秩矩阵完成）;开发快速算法来评估这些拟阵的秩函数。所要求的资金是在未来两年内对东京进行四次为期一个月的访问，并出席几次会议和讲习班，以传播我们的成果并获得宝贵的反馈。

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.