Abstract rigidity for natural stability problems

自然稳定性问题的抽象刚性

• 批准号: EP/X036723/1
• 负责人: Anthony Nixon
• 金额: $ 54.63万
• 依托单位: Lancaster University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX036723%2F1
• 关键词: Abstract; rigidity; natural; stability; problems

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.

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