Counting linear extensions of restricted posets

2018/02/17 by Dittmer, Samuel, Pak, Igor · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1802.06312

Abstract

The classical 1991 result by Brightwell and Winkler states that the number of linear extensions of a poset is #P-complete. We extend this result to posets with certain restrictions. First, we prove that the number of linear extension for posets of height two is #P-complete. Furthermore, we prove that this holds for incidence posets of graphs. Finally, we prove that the number of linear extensions for posets of dimension two is #P-complete.

Cited by

• Generating uniform linear extensions using few random bits

Related

• Linear extensions of finite posets
• Counting linear extensions of posets with determinants of hook lengths
• Linear extension numbers of n-element posets
• Optimizing Linear Extensions
• The bounds for the number of linear extensions via chain and antichain coverings