W&M Featured Events
[PAST EVENT] Mathematics Colloquium: Nathan Williams (University of California, Santa Barbara)
Abstract: I will discuss three combinatorial problems with the same solution.
In 2002, R. Suter defined a striking cyclic symmetry of order n+1 on the subposet of Young?s lattice consisting of the 2^n partitions with largest hook at most n. These partitions naturally arise from D. Peterson's parametrization of abelian ideals of a Borel subalgebra using the affine Weyl group (as told by B. Kostant); the cyclic symmetry comes from the fact that the affine Dynkin diagram in type A is a cycle.
Problem 1. Describe the orbit structure of Suter's cyclic symmetry.
Now let Dyck(a,b) be the set of lattice paths from (0,0) to (b,a) that stay above the main diagonal. The sweep map--defined by D. Armstrong, N. Loehr, and G. Warrington--is a map from Dyck(a,b) to itself that rearranges the steps of a path according to the order in which they are encountered by a line of slope a/b sweeping down from above. This map has applications in the theory of Macdonald polynomials and diagonal harmonics---it generalizes the zeta map on Dyck(a,a+1), which converts between J. Haglund's statistic bounce and M. Haiman's dinv.
Problem 2. Show that the sweep map is a bijection on Dyck(a,b).
Finally, consider the following problem of scheduling daily, recurring tasks. The day is divided into m hours, and there are N tasks to be carried out each day (numbered, or prioritized, from 1 to N). For simplicity, suppose that the total amount of time required to carry out all of the tasks is some multiple of m. Each task takes an integer number of hours to complete: a task can take zero hours, but no task takes as much as an entire day. Tasks start on the hour, and cannot be interrupted once started. Tasks can be worked on concurrently, and the starting order for the tasks within the day is specified--the jth task must start before or at the same time as the (j+1)st task. The schedule repeats every day, so tasks can start at the end of one day and finish at the beginning of the next day.
Problem 3. With these assumptions, find an assignment of starting hours for the tasks so that the workload throughout the day is constant.
This is based on joint work with Hugh Thomas.
Contact
Gexin Yu