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.
