Weak orders admitting a perpendicular linear order (Q861798)

The authors characterize the finite weak orders admitting a perpendicular linear order and give two basic results. First, every linear order having at least four elements has a perpendicular linear order and, second, if \(q(n)\) denotes the number of linear orders perpendicular to the natural order on \([1, \ldots, n]\), then \(\lim_{n \rightarrow \infty} \frac{q(n)}{n!} = e^{-2} = 0,1353\ldots\). The main result of this paper, Theorem 3, gives necessary and sufficient conditions for a weak order \(P\) to admit a perpendicular linear order \(L\). Essentially Theorem 3 says that such a linear order exists if and only if the levels of \(P\) are not ``too big''.