[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Kevin Milans (West Virginia University)

February 9, 2018
2pm - 3pm
Jones Hall, Room 302
200 Ukrop Way
Williamsburg, VA 23185Map this location
Access & Features
  • Open to the public

Mathematics Colloquium and EXTREEMS-QED Lecture: Kevin Milans (West Virginia University)

Title:  First-Fit chain partitions in partially ordered sets

Abstract: A partially ordered set, or poset, is a set $P$ and a relation $\le$ on $P$ that is reflexive, antisymmetric, and transitive. Posets can be used, for example, to model a set of tasks where in some cases, a task $w$ must be performed before task $x$ (as indicated by the relation $w \le x$), and in other cases, the order of performing tasks $y$ and $z$ is unimportant.

A chain in a poset is a set of pairwise comparable points (i.e. the tasks must be performed in a particular order), and an antichain is a set of points that is pairwise incomparable (i.e. the order is completely arbitrary). The width of a poset is the maximum size of an anthichain. Dilworth's theorem states that for each poset $P$, the minimum size of a partition of $P$ into chains equals the width of $P$.

Dilworth's theorem produces optimal chain partitions by carefully looking at the whole poset before making decisions about how to assign points to chains. In contrast, the First-Fit algorithm produces a chain partition in the simplest way imaginable. First-Fit processes the points of P in some order, and assigns each point in turn to the earliest available chain in which it fits, creating a new chain if necessary.

We are interested in how the performance of First-Fit compares to the optimal performance of Dilworth's theorem. In general, First-Fit behaves poorly in comparison.  However, when $P$ is known to avoid certain subposets $Q$, the behavior of First-Fit becomes subtle and interesting. 

Let $\textrm{FF}(w,Q)$ be the maximum size of a First-Fit chain partition on a poset $P$ of width $w$ that does not contain $Q$ as a subposet.  Bosek, Krawczyk, and Matecki proved that $\textrm{FF}(w,Q)$ is finite if and only if $w=1$ or $Q$ has width at most $2$.  We characterize the family of posets $Q$ for which $\textrm{FF}(w,Q)$ is subexponential in $w$. This is joint work with Michael Wigal.


Gexin Yu