Average relational distance in linear extensions of posets

作者：Brightwell Graham; Patel Viresh^*

来源：Discrete Mathematics, 2010, 310(5): 1016-1021.

DOI：10.1016/j.disc.2009.10.016

• Linear extensions of posets
• Linear arrangement problem

We consider a natural analogue of the graph linear arrangement problem for posets. Let P = (X, <) be a poser that is not an antichain, and let lambda : X -> vertical bar n vertical bar 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 lambda is lambda(b) - lambda(a). The average relational distance of lambda(1) denoted dist(P)(lambda), 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)(lambda) in polynomial time. Furthermore, we show that this maximum is at least 1/3 (vertical bar X vertical bar + 1), and this bound is extremal.

• 出版日期2010-3-6