Submodular Percolation: A Proposal for Research in Combinatorics

子模渗滤：组合学研究的提案

• 批准号: 0600876
• 负责人: Peter Winkler
• 金额: --
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600876&HistoricalAwards=false
• 关键词: Submodular; Percolation; Proposal; Research; Combinatorics

The proposer seeks to explore a combinatorial thread which involves algorithms, optimization and statistical physics; and in particular, connects process scheduling, submodular systems, and a form of percolation. The problem of scheduling two real sequences so as to minimize their maximum pairwise sum leads to a preorder on sequences, called the ``worm order.'' Remarkably, for any submodular function on a finite distributive lattice, there is a maximal chain whose function values are minimum in the worm order relative to all paths from 0 to 1 in the lattice. One consequence is explicit representation of the theta function for a form of coordinate percolation, in which random reals are assigned to axis points on the plane grid, and grid points inherit the sum of the two reals assigned to their coordinates. Points whose value exceeds some bound are deleted, and the theta function measures the probability that one can walk to infinity on what remains of the grid.The proposed line of research aims to better understand percolation, originally a model for physical processes such as water seeping through a porous material. However, a variety of additional applications arise when a complex process must be scheduled, and the issue is whether backward steps are needed. For example, if the components of a computer system must be upgraded, is it possible that a temporary downgrade will be needed at some point to keep things running smoothly? If a line of searchers are sweeping a forest in search of a lost child, can they do so without covering any area more than once? The proposed work will identify conditions under which one can guarantee that, if the process can be accomplished at all, then it can be done without retreating.

提议者试图探索一个组合线程，涉及算法，优化和统计物理;特别是，连接过程调度，子模块化系统，和一种形式的渗透。 调度两个真实的序列以使它们的最大成对和最小化的问题导致序列上的一个前序，称为“蠕虫序”。值得注意的是，对于有限分配格上的任何子模函数，存在一个极大链，其函数值相对于格中从0到1的所有路径在蠕虫顺序中最小。 一个结果是明确表示的theta函数的一种形式的坐标渗流，其中随机实数分配给轴点的平面网格，网格点继承的总和分配给他们的坐标。 值超过某个界限的点会被删除，theta函数衡量一个人可以在网格剩余部分上行走到无限远的概率。拟议的研究路线旨在更好地理解渗透，最初是物理过程的模型，例如水渗透通过多孔材料。 然而，当必须调度复杂的过程时，会出现各种其他应用程序，问题是是否需要向后步骤。例如，如果计算机系统的组件必须升级，是否有可能在某个时候需要临时降级以保持系统平稳运行？ 如果一队搜索者正在森林里搜寻一个迷路的孩子，他们能在不超过一次的情况下搜索任何区域吗？ 拟议的工作将确定在哪些条件下可以保证，如果这一进程能够完成，那么就可以毫不退缩地完成。