Order Preserving Maps and Linear Extensions of a Finite Poset

Jacqueline Daykin, David Daykin

Research output: Contribution to journalArticlepeer-review


We study order preserving maps from a finite poset to the integers. When these maps are bijective they are called linear extensions. For both kinds we give many elementary properties and inequalities. A positive correlation inequality was proved by Graham, Yao and Yao. Then contributions were made by Graham, Kleitman, Shearer, Shepp and others. We obtain the corresponding negative correlation inequalities. Most authors have used the FKG inequality; we use an inequality of Daykin instead. Graham made a conjecture concerning range posets so we characterise these, and prove various cases of the conjecture. Finally we give necessary and sufficient conditions for a map defined on a subposet to extend to the whole poset. The results have applications in computer science.
Original languageEnglish
Pages (from-to)738-748
Number of pages11
JournalSIAM Journal on Algebraic Discrete Methods
Issue number4
Publication statusPublished - 1985


Dive into the research topics of 'Order Preserving Maps and Linear Extensions of a Finite Poset'. Together they form a unique fingerprint.

Cite this