×

Approximation of average ranks in posets. (English) Zbl 1265.05592

Summary: Objects that are described by attribute vectors often need to be ranked. A popular approach not requiring subjective assumptions ranks the objects on the basis of their average rank in the linear extensions of the induced partially ordered set, or poset for short. Since the exact computation of average ranks in posets with many incomparable objects is infeasible with current technology, approximations are required. We introduce a new formula that approximates the average ranks more accurately than presently known formulae.

MSC:

05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)