The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons

The expected number of pairwise comparisons needed to learn a partial order on n elements is shown to be at least nn/4-o(nn), and an algorithm is given that needs only nn/4+o(nn) comparisons on average. In addition, the optimal strategy for learning a poset with four elements is presented.