
Discrete Mathematics and Optimization Seminar

Monday, Sept. 27th, 2010
The Worm Order and its Applications
Peter Winkler
Dartmouth

Abstract:
Let x and y be two words in a linearlyordered alphabet
(such as the real numbers). We say that x is below y in
the worm order if they can be "scheduled" in such a way that
x is always less than or equal to y.
It turns out that in any submodular system there is a
maximal chain that is minimal in the worm order, among all
paths from 0 to 1. One consequence is a set of general
conditions under which parallel scheduling can be done without
backward steps.
Among the applications are a fast algorithm for scheduling
multiple processes without overusing a resource; a theorem about
searching for a lost child in a forest; and a closedform expression
for the probability of escaping from the origin in a form of
coordinate percolation.
Joint work in part with Graham Brightwell (LSE) and in part
with Lizz Moseman (USMA).



