#

### Volume 2014

#### Article 3

Published by the Department of Computer Science, The University of Chicago.

#### Near-linear time simulation of linear extensions of a
height-2 poset with bounded interaction

Mark Huber

Claremont McKenna College

Claremont CA

USA

`mhuber AT cmc.edu`

*June 8, 2014*
#### Abstract

A linear extension of a poset $([n],\preceq)$
is a permutation
$\sigma$ such that if $\sigma(i) \preceq \sigma(j)$, then $i \leq j$.
The problem considered here is sampling uniformly
from the set of linear extensions. The best known algorithm for the
general problem requires time $O(n^3\ln n)$.
This work presents the first new method that
is provably faster for a nontrivial class of posets. Specifically,
when the poset
is height-2 (so there do not exist distinct elements with
$i \preceq j \preceq k$)
and has bounded interaction (so for each $i$ there are at most
$\Delta$ elements $i'$ with $i \preceq i'$ or $i' \preceq i$), then the
new algorithm runs in time $O(n\Delta^2 \ln n)$. Such posets arise
naturally as corrugated surfaces on graphs, where $\Delta - 1$ is the
maximum degree of the graph. Therefore, finding corrugated surfaces on
a fixed family of lattices takes $O(n \ln n)$ (near-linear time.) The
ability to sample from the set of linear extensions can be used to build
approximation algorithms for counting the number of linear extensions.
Using the new method, an approximation scheme that counts the number of
linear extensions to within a factor of $1 + \epsilon$ with fixed probability
runs in $O(n^2 \Delta^2 [\ln n]^6\epsilon^{-2})$ time.

- The article:
**PDF** (268 KB)
- Source material: ZIP (84 KB)
**BibTeX** entry for this article (306 bytes)

Submitted November 10, 2012, revised May 24, 2014, published June 8,2014.

Article 2
Volume 2014
Published articles