Submodular Percolation: A Proposal for Research in Combinatorics

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

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.