Collaborative Research: Exploring the Space of Large Knots and Links

合作研究：探索大结和链接的空间

• 批准号: 0712997
• 负责人: Claus Ernst
• 金额: --
• 依托单位: Western Kentucky University Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0712997&HistoricalAwards=false
• 关键词: Collaborative; Research; Exploring; Space; Large

The PIs propose to investigate the space of very large knots (with thousands of crossings) through a symbiosis of theoretical research and computation. The problems raised here are motivated by the applications of knot theory in chemistry, physics, and biophysics. The main goal is to develop and implement new algorithms that sample the space of large knots and that are capable of embedding large knots tightly or semi-tightly in the simple cubic lattice. In this research, theoretical work will enhance the algorithms to be developed and the empirical results will support the theoretical approaches. The proposed research project consists of several inter-related objectives: developing fast algorithms capable of generating representative samples of large knot diagrams, developing better algorithms capable of embedding large knots tightly in the simple cubic lattice, and developing new theoretical approaches to improve the upper and lower bounds of the ropelength in general or for special knot classes such as alternating knots. These objectives are difficult and challenging. For example, the distribution of large knots is unknown, determining the crossing number of large non-alternating knots is known to be NP-hard, and theoretical results concerning large knots are scarce in general. Concretely the PIs expect to sample the space of large knots using and comparing three approaches: first applying uniform prefix vectors to generate large Hamiltonian prime knot diagrams; second, adapting a method based on uniform random polygons to sample large prime knot diagrams; finally, using graph tensor products to construct large non-alternating knots whose crossing number can be approximated by computing the breadth of the Jones polynomial (via the Tutte polynomial); sampling such non-alternating knots allows a comparison with alternating knots of similar size. Furthermore, the PIs will work on developing a more efficient embedding algorithm by extending the constructive proof of two of the PIs regarding the embedding length of closed braids to general knots. This approach also aims at improving the general upper bound on the ropelength of knots from the current bound of crossing number to the power of 1.5. The main subjects to be studied in this proposal are large physical knots, i.e. large knots that can actually occur in the real world. Examples of such occurrences are long, knotted polymer chains or circular DNA. The problems raised in this proposal are motivated by the applications of knot theory in chemistry, physics and biophysics. For example, DNA knots formed under extreme conditions of condensation, such as those found in bacteriophage P4, can be quite large. Such large and tightly packed circular DNAs are difficult to analyze experimentally. Theoretical results or computational simulations on such systems would be of great help. Yet theoretical studies on large knots are scarce. The proposed project aims at gaining more knowledge about large knots: How much space is needed in order to pack certain large knots? How efficiently can knots be packed tightly? Is there a difference between packing a complicated knot in comparison to packing a simple knot? What role does the topology (shape) of the knot play? The PIs intend to develop computer programs that can generate large knots and pack them tightly, based on theoretical results and algorithms they have developed in the past. Empirical data can then be gathered through the repeated applications of these programs. The proposed activities may have significant implications in DNA research, polymer science, and other sciences. The activities will result in tools for researchers to compute various geometric and topological characteristics of the large knots they encounter in their field and thus help them to better understand biological and physical systems where large knotted molecules occur.

pi建议通过理论研究和计算的共生关系来研究超大结（有数千个交叉点）的空间。这里提出的问题是由结理论在化学、物理和生物物理学中的应用所引起的。主要目标是开发和实现新的算法，对大节点的空间进行采样，并能够在简单立方晶格中紧密或半紧密地嵌入大节点。在本研究中，理论工作将加强有待开发的算法，实证结果将支持理论方法。提出的研究项目包括几个相互关联的目标：开发能够生成大结图代表性样本的快速算法，开发能够在简单立方晶格中紧密嵌入大结的更好算法，以及开发新的理论方法来改进一般绳长或特殊绳结类（如交替绳结）的上下界。这些目标既困难又具有挑战性。例如，大结的分布是未知的，确定大的非交替结的交叉数是已知的NP-hard，关于大结的理论结果通常是稀缺的。具体来说，pi期望使用并比较三种方法对大结空间进行采样：首先使用一致前缀向量生成大哈密顿素数结图；其次，采用基于均匀随机多边形的方法对大型素数结图进行采样；最后，利用图张量积构造大型非交变结点，其交叉数可以通过计算Jones多项式的宽度来近似（通过Tutte多项式）；抽样这样的非交替结可以与类似大小的交替结进行比较。此外，pi将致力于开发一种更有效的嵌入算法，将两个pi关于闭合辫的嵌入长度的建设性证明扩展到一般结。该方法还旨在提高结绳长度的一般上界，使之从目前的交叉数的上界提高到1.5的次幂。本提案中要研究的主要主题是大型物理结，即在现实世界中实际可能发生的大型结。这种情况的例子是长，打结的聚合物链或环状DNA。本提案中提出的问题是由结理论在化学、物理和生物物理学中的应用所引起的。例如，在极端凝结条件下形成的DNA结，比如在噬菌体P4中发现的那些，可能相当大。这种大而紧密排列的环状dna很难在实验中进行分析。这类系统的理论结果或计算模拟将大有帮助。然而，关于大结的理论研究很少。拟议的项目旨在获得更多关于大结的知识：为了包装某些大结需要多少空间？打结的效率如何？包装一个复杂的结和包装一个简单的结之间有什么区别吗？结的拓扑（形状）起什么作用？pi打算开发计算机程序，根据他们过去开发的理论结果和算法，可以产生大的结并将它们紧密地组合在一起。然后可以通过这些程序的重复应用收集经验数据。提议的活动可能对DNA研究、聚合物科学和其他科学有重大影响。这些活动将为研究人员提供工具，以计算他们在研究领域中遇到的大结的各种几何和拓扑特征，从而帮助他们更好地理解发生大结分子的生物和物理系统。