# zbMATH — the first resource for mathematics

Exploiting the lattice of ideals representation of a poset. (English) Zbl 1110.06001
The authors demonstrate how some graph counting operations on the ideal lattice representation of a poset $$P$$ can be used to count the number of linear extensions of $$P$$, the rank probabilities for every $$x$$ of $$P$$, the mutual rank probabilities Prob$$(x>y)$$ for every $$(x,y)$$ in $$P^2$$, and to randomly generate a linear extension of $$P$$. They establish simple and fast algorithms for generating a random linear extension and deriving (mutual) rank probabilities of a poset. Since each of the mentioned problems is known to reside in the class $$\#\text{P}$$-complete counting problems and since ideal lattice representation of a poset can be obtained in constant amortized time, the proposed approach favours the standard approach consisting in exhaustive enumeration of all linear extensions.

##### MSC:
 06A06 Partial orders, general 06A07 Combinatorics of partially ordered sets 06A05 Total orders 68Q25 Analysis of algorithms and problem complexity 68W05 Nonnumerical algorithms