Arts & Sciences Events
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Kevin Milans (West Virginia University)
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.
Contact
Gexin Yu