Combinatorial Methods for Random Structures in the Plane

平面内随机结构的组合方法

• 批准号: 0901475
• 负责人: Peter Winkler
• 金额: $ 17万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0901475&HistoricalAwards=false
• 关键词: Combinatorial; Methods; Random; Structures; Plane

ABSTRACTPrincipal Investigator: Winkler, Peter Proposal Number: DMS - 0901475Institution: Dartmouth CollegeTitle: Combinatorial Methods for Random Structures in the PlaneThe PI will tackle three random models in the plane, all of which show signs of benefiting from the application of combinatorial techniques. The first of these concerns branched polymers; the second, hard-core gases; the third, coordinate percolation. Branched polymers are connected configurations of spheres in space; their partition functions can be computed combinatorially in dimensions 2 and 3. Hard-core gases are random sets of non-overlapping spheres in space; here the PI has some ideas for discrete versions which may help in proving the existence of a solid-state phase. Finally, combinatorial techniques applied to coordinate percolation, in which the life of a site depends on events associated with the lines that cross there, has already yielded an exact expression for percolation probability.The three models are connected to applications in biochemistry, physics and computer science. Complex tree-like forms of proteins, hemoglobins, and molecules involved in photosynthesis can be compared with random mathematical ``branched polymers'' to help discern the presence of unsuspected forces or constraints. Formation of crystal structures should, in theory, resemble what happens to collections of hard spheres when they are compressed on the plane or in space---but this simple mathematical model is not yet fully understood. Finally, scheduling processes (such as computer programs) to avoid conflict is modeled by avoiding collisions in random walks, one of several applications of coordinate percolation. The PI's approach is to use combinatorial methods---rougly speaking, sophisticated means of counting and manipulating discrete objects---to better understand all three models.

主要调查者：温克勒，彼得提案编号：DMS-0901475机构：达特茅斯学院标题：平面中随机结构的组合方法PI将处理平面上的三个随机模型，所有这些模型都显示出受益于组合技术应用的迹象。第一种是支化聚合物；第二种是硬核气体；第三种是配位渗流。支化聚合物是空间中球体的连通构型；它们的配分函数可以在2维和3维中组合计算。硬核气体是空间中不重叠的球体的随机集合；在这里，PI提出了一些离散形式的想法，这可能有助于证明固态相的存在。最后，应用于协调渗流的组合技术已经给出了渗流概率的精确表达式。这三个模型与生物化学、物理和计算机科学的应用有关。复杂的树状蛋白质、血红蛋白和参与光合作用的分子可以与随机的数学“支化聚合物”进行比较，以帮助识别是否存在意想不到的力或限制。理论上，晶体结构的形成应该类似于硬球体在平面上或空间中被压缩时发生的事情-但这个简单的数学模型还没有完全被理解。最后，通过避免随机行走中的碰撞来模拟避免冲突的调度过程(如计算机程序)，这是坐标渗流的几个应用之一。PI的方法是使用组合方法-粗略地说，是计算和处理离散对象的复杂手段-以更好地理解所有这三个模型。