Order Preserving Maps and Linear Extensions of a Finite Poset

Authors Organisations
Type Article
Original languageEnglish
Pages (from-to)738-748
Number of pages11
JournalSIAM Journal on Algebraic Discrete Methods
Volume6
Issue number4
DOI
Publication statusPublished - 1985
Permanent link
View graph of relations
Citation formats

Abstract

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.