Near-linear time uniform sampling from some height-2 linear extensions

03/20/2018 - 12:15pm
03/20/2018 - 1:10pm
Mark Huber (CMC)

Given a partially ordered set (poset), a linear extension is a total ordering of the elements that respects the partial ordering. For example, if $1\preceq 2$ and $3 \preceq 4$, then $1 \sqsubseteq 3 \sqsubseteq 2 \sqsubseteq 4$ is a valid linear extension (write $1324$ for simplicity) while $3 \sqsubseteq 2 \sqsubseteq 4 \sqsubseteq 1$ (3241 for short) is not because it does not respect $1 \preceq 2$. All partial orders have at least one linear extension, but in general counting the number of linear extensions of a poset is a #P complete problem. Dittmer & Pak recently showed that this holds even for posets where no three different elements form a chain $i \prec j \prec k$. This is called a height 2 poset. So counting exactly is very difficult, even in this restrictive case. However, if one can sample uniformly from the set of linear extensions, then they can approximately count the number of linear extensions. In this talk I will present a method for sampling uniformly from the linear extensions of a height-2 poset that runs in time $O(n \ln(n) \Delta^2)$, where $\Delta$ is an upper bound on the number of elements comparable to an arbitrary element $i$. This improves upon the previously best known running time of $O(n^3 \ln(n))$.

Millikan 2099, Pomona College

Claremont Graduate University | Claremont McKenna | Harvey Mudd | Pitzer | Pomona | Scripps
Proudly Serving Math Community at the Claremont Colleges Since 2007
Copyright © 2018 Claremont Center for the Mathematical Sciences