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

February 9, 2018
2pm - 3pm
##### Location
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