Collaborative Research: Exploring the Space of Large Knots and Links

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

• 批准号: 0712958
• 负责人: Yuanan Diao
• 金额: $ 4.27万
• 依托单位: University of North Carolina at Charlotte
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0712958&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建议通过理论研究和计算的共生来研究非常大的节点（具有数千个交叉点）的空间。这里提出的问题是由纽结理论在化学，物理学和生物物理学中的应用所激发的。我们的主要目标是开发和实现新的算法，采样的大节点的空间，并能够嵌入大节点紧密或半紧密的简单立方晶格。在这项研究中，理论工作将提高算法的开发和实证结果将支持理论方法。拟议的研究项目包括几个相互关联的目标：开发快速算法，能够产生代表性样本的大节点图，开发更好的算法，能够嵌入大节点紧密的简单立方晶格，并开发新的理论方法，以提高ropelength的上限和下限一般或特殊的结类，如交替结。这些目标是困难和具有挑战性的。例如，大纽结的分布是未知的，确定大的非交替纽结的交叉数是已知的NP-难，并且关于大纽结的理论结果通常是稀缺的。具体而言，PI希望使用并比较三种方法对大节的空间进行采样： 首先利用统一前缀向量生成大的Hamilton素纽结图，然后采用基于均匀随机多边形的方法对大的素纽结图进行采样，最后利用图张量积构造大的非交错纽结，其交叉数可以通过计算Jones多项式的宽度来近似（通过Tutte多项式）;对这种非交替结进行采样允许与类似大小的交替结进行比较。 此外，PI将致力于开发一个更有效的嵌入算法，通过扩展两个PI关于封闭编织的嵌入长度的构造性证明到一般结。该方法的目的还在于提高一般的ropellength的上限从目前的交叉数的上限为1.5的幂。在这个提议中要研究的主要课题是大的物理结，即实际上可以在真实的世界中发生的大的结。这种情况的例子是长的、打结的聚合物链或环状DNA。这个提议中提出的问题是由纽结理论在化学、物理和生物物理中的应用所激发的。例如，在极端的凝聚条件下形成的DNA结，如在噬菌体P4中发现的那些结，可以相当大。如此大且紧密堆积的环状DNA很难通过实验进行分析。对这种系统的理论结果或计算模拟将有很大的帮助。然而，对大纽结的理论研究却很少。拟议的项目旨在获得更多关于大节的知识：为了包装某些大节需要多少空间？如何有效地可以结紧密包装？包装一个复杂的结和包装一个简单的结有什么区别吗？结的拓扑（形状）起什么作用？PI打算根据他们过去开发的理论结果和算法开发可以生成大结并将其紧密包装的计算机程序。然后，通过反复应用这些程序，可以收集经验数据。拟议的活动可能对DNA研究、聚合物科学和其他科学产生重大影响。这些活动将为研究人员提供工具，以计算他们在其领域中遇到的大型结的各种几何和拓扑特征，从而帮助他们更好地了解大型结分子发生的生物和物理系统。