Abstract rigidity for natural stability problems

该项目将在僵化的共同语言理论下提出以下四个看似完全不同的问题。拿一个三角形和一个正方形。三角形是刚性的：其角度由其边的长度确定。正方形是灵活的：您可以将其变形为钻石形状，而无需更改其边缘的长度。如何确定更复杂结构的刚性或灵活性？2.假设给出一个矩形数组中条目的子集，并想要推断剩余的值。假设数组作为一个矩阵具有某种特定的低阶，即使在仅有令人惊讶的少量条目的情况下，这个问题也很容易处理。这个矩阵补全问题是Netflix、Amazon和其他公司使用的推荐系统算法的核心。考虑一下遗传网络。一个人寻求一个可能涉及大量基因的模型，而从几个人身上提取基因表达数据是可行的。这种现象经常出现在统计应用中：问题涉及大量随机变量，但由于收集数据样本的困难或费用，只有少量的观测数据。这引发了这样一个问题：在图形模型中，保证协方差矩阵的最大似然估计存在所需的最小观测次数是多少？4.基因组在细胞核中的空间组织在包括DNA复制和基因调控在内的许多细胞过程中起着重要作用。这推动了重建基因组3D结构的方法的发展。了解、分析和确定通过实验观察或推断的接触频率信息可能出现的构型的性质，可以影响单倍体和二倍体生物体的形式和功能。这些问题有什么共同之处？这个项目将表明，它们都可以用图形刚性理论的推广来研究。图的刚性是一个跨学科的领域，其目的是提供识别离散几何结构的刚性和柔性属性的技术。结构可以被认为是具有连接接头的刚性积木的组件，并且通常根据这些积木和接头的性质来分类；例如，杆和关节、主体和杆以及板和铰链框架。这些形式的约束系统在自然界中普遍存在(例如蛋白质中的周期性结构、病毒衣壳中的对称性和材料的分析)，在工程中(例如十段、连接和可展开结构)和在技术中(例如多智能体系统的队形控制、传感器网络局部化和CAD)。为了涵盖所有这四个问题，该项目将发展超图的广义刚性理论，然后研究出现的新的拟阵家族。拟阵是惠特尼在20世纪30年代引入的一种数学结构。它们扩展了一组向量的线性独立性的概念，并在运筹学和组合优化中有许多重要的应用。在我们的广义刚性模型中，定义问题是：结构是唯一的(全局刚性)；存在满足给定约束的有限数量的实现(刚性)；还是存在无限多的实现(灵活性)。确定给定结构何时是(全局)刚性的是NP困难的，即它属于一类被广泛认为没有有效解决方案的问题。然而，该项目将使用新的组合和刚性理论技术来有效地解决一般情况，适用的概率很高，当应用程序受到噪声或测量误差影响时尤其有用。这些进展将使更大的结构能够在刚性应用的范围内进行分析。

The project will cast the following four seemingly disparate problems under the common language of rigidity theory.1. Take a triangle and a square. The triangle is rigid: its angles are determined by the lengths of its edges. The square is flexible: you can deform it into a diamond-shape without changing the lengths of its edges. How do you determine the rigidity or flexibility of more complicated structures?2. Suppose one is given a subset of entries from a rectangular array and would like to infer the remaining values. Assuming that the array, as a matrix, has some specific low rank makes this problem tractable even when only surprisingly few entries are known. This matrix completion problem is at the heart of recommendation system algorithms used by Netflix, Amazon and others.3. Consider genetic networks. One seeks a model potentially involving a vast number of genes, while it is only viable to extract gene expression data from a few individuals. This phenomenon occurs often in statistical applications: problems involve a large number of random variables, but only a small number of observations due to difficulty, or expense, in collecting samples of the data. This motivates the question, what is the minimum number of observations needed to guarantee the existence of the maximum likelihood estimator of the covariance matrix in a graphical model?4. The spatial organization of the genome in the cell nucleus plays an important role for many cellular processes including DNA replication and gene regulation. This motivates the development of methods to reconstruct the 3D structure of the genome. Understanding, analysing and identifying the nature of the configurations that can occur from experimentally observed, or inferred, contact frequency information can impact on the form and function of haploid and diploid organisms. What do these problems have in common? This project will show they can all be studied using a generalisation of the theory of graph rigidity. 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, linkages and deployable structures) and in technology (e.g. formation control for multi-agent systems, sensor network localisation and CAD).In order to encompass all four problems, the project will develop a generalised rigidity theory for hypergraphs and then study the new families of matroids that emerge. 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 our generalised rigidity model, the defining questions 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). Determining when a given structure is (globally) 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, the project will use novel combinatorial and rigidity theoretic techniques to efficiently resolve generic cases, applicable with high probability, and especially useful when the applications are subject to noise or measurement error. These advances will allow larger structures to be analysed across the spectrum of rigidity applications.