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.

摘要原理研究者：Winkler，Peter提案编号：DMS -0901475机构：Dartmouth Collegetitle：PlaneThe Pi中随机结构的组合方法的组合方法将在飞机上处理三个随机模型，所有这些模型均显示出所有受益于组合技术的受益迹象。 这些关注的第一个分支聚合物；第二个硬核气体；第三个坐标渗透。 分支聚合物是空间中球体的连接配置；它们的分区函数可以在维度2和3中进行组合计算。硬核气体是空间中非重叠球体的随机集。在这里，PI对离散版本有一些想法，这些想法可能有助于证明存在固态阶段的存在。 最后，应用于协调渗透的组合技术，其中站点的寿命取决于与跨越的线相关的事件，已经产生了渗透概率的精确表达。这三个模型与生物化学，物理学，物理学和计算机科学中的应用有关。 可以将参与光合作用的蛋白质，血红蛋白和分子的复杂树状形式与随机的数学``分支聚合物''进行比较，以帮助辨别出未悬而未决的力或约束的存在。 从理论上讲，晶体结构的形成应类似于硬球在平面或太空中压缩时的收集，但这种简单的数学模型尚未完全理解。 最后，调度过程（例如计算机程序）避免冲突是通过避免随机步行中的碰撞而建模的，这是坐标渗透的几种应用之一。 PI的方法是使用组合方法 - - 计数和操纵离散对象的精致手段，以更好地理解所有三个模型。