Given a set of values $X=\{x_1,x_2,…,x_m\}$. I want to construct an irreflexive, transitive total order relation $>$ by doing pairwise comparisons among the values of $X$.
From trail and error I got $m-1$ comparisons needed. For values less than $m-1$, I can find an extension of the partial order. Does $m-1$ is the maximum number of comparisons needed to define a total order over $m$ values?
On
No, you are trying to sort the elements. The best comparison sort algorithms are of order $n \log n$. For 3 elements, in the worst case you need a minimum of 3 comparisons. Of course, you could get lucky and do the right two first. Say you find $x_1 \gt x_2$. If your next comparison gives $x_1 \gt x_3$ or $x_2 \lt x_3$ you don't know the complete order.
It seems to me like $m-1$ comparisons will be necessary and sufficient.
If you think about the Hasse diagram for a totally ordered poset, it's basically a vertical path graph. If it has $m$ nodes, then it must have $m-1$ edges, or comparisons. Any fewer and your Hasse diagram is disconnected, any more and you will end up with redundant comparisons.