Average relational distance in linear extensions of posets

We consider a natural analogue of the graph linear arrangement problem for posets. Let P = ( X , ≺ ) be a poset that is not an antichain, and let λ : X → [ n ] be an order-preserving bijection, that is, a linear extension of P . For any relation a ≺ b of P , the distance between a and b in λ is λ ( b ) − λ ( a ) . The average relational distance of λ , denoted dist P ( λ ) , is the average of these distances over all relations in P . We show that we can find a linear extension of P that maximises dist P ( λ ) in polynomial time. Furthermore, we show that this maximum is at least 1 3 ( | X | + 1 ) , and this bound is extremal.