Counting Linear Extensions of Restricted Posets

  • Sam Dittmer
  • Igor Pak
DOI: https://doi.org/10.37236/8552

Abstract

We prove the 1991 conjecture by Brightwell and Winkler that counting the number of linear extensions for posets of height two is #P-complete. We further extend this result to incidence posets of graphs.

Published
2020-12-11
How to Cite
Dittmer, S., & Pak, I. (2020). Counting Linear Extensions of Restricted Posets. The Electronic Journal of Combinatorics, 27(4), P4.48. https://doi.org/10.37236/8552
Issue
Volume 27, Issue 4 (2020)
Article Number
P4.48