On the Queue-Number of Partial Orders

The queue-number of a poset is the queue-number of its cover graph viewed as a directed acyclic graph, i.e., when the vertex order must be a linear extension of the poset. Heath and Pemmaraju conjectured that every poset of width w has queue-number at most w. Recently, Alam et al. constructed posets of width w with queue-number w+1. Our contribution is a construction of posets with width w with queue-number $\Omega(w^2)$. This asymptotically matches the known upper bound.