Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, September 26, 2006 - 4:00pm

Peter Winkler

Dartmouth College

Location

University of Pennsylvania

4N30

Scheduling sequences of reals to minimize their maximum sum leads naturally to a partial order on real words which we call the "worm order". We show that in any submodular system there is a maximal chain which is minimum in the worm order among all paths from 0 to 1; this results in conditions under which a process can be scheduled without taking backward steps, and also enables us to analyze a form of coordinate percolation. Joint work with Graham Brightwell (LSE) and in part with Lizz Moseman (Dartmouth).