## When is counting linear extensions easy?

- Sept. 23, 2013
- 3:15 p.m.
- LeConte 312

## Abstract

A now-classic result of Brightwell and Winkler is that counting linear extensions for general posets is #P-hard. It is well-known that counting antichains is also #P-hard (Provan-Ball), but that this can be done in polynomial time for dimension 2 posets (M\"ohring). For which classes of posets is counting linear extensions easy in the aforementioned sense? We introduce a new class, bwisic (an acronym for ``bounded width indecomposable strong interval condition'') posets, generalizing series-parallel posets, for which we provide a polynomial-time algorithm to count the number of linear extensions.