On Unimodality for Linear Extensions of Partial Orders
Fan Chung, P. C. Fishburn, Ronald Graham · SIAM Journal on Algebraic and Discrete Methods · 1980
R. Rivest has recently proposed the following intriguing conjecture: Let $x^* $ denote an arbitrary fixed element in an n-element partially ordered set P, and for each k in $\{ 1,2, \cdots ,n \}$ let $N_k $ be the number of order-preserving maps from P onto $\{ 1,2, \cdots ,n \}$ that map $x^* $ into k. Then the sequence $N_1 , \cdots ,N_n $ is unimodal. This note proves the conjecture for the special case in which P can be covered by two linear orders. It also generalizes this result for P that have disjoint components, one of which can be covered by two linear orders.