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
Issue
Volume 27, Issue 4 (2020)
Article Number
P4.48