IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC