Daykin, Jacqueline (1984) Monotonic functions of finite posets. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Daykin_1984.pdf - Unspecified Version - Requires a PDF viewer. Download (4Mb) | Preview

Request Changes to record.

Abstract

Classes of monotone functions from finite posets to chains are studied. These include order-preserving and strict order-preserving maps. When the maps are required to be bijective they are called linear extensions. Techniques for handling the first two types are closely related; whereas for linear extensions quite distinct methods are often necessary, which may yield results for order-preserving injections.

First, many new fundamental properties and inequalities of a combinatorial nature are established for these maps. Quantities considered here include the range, height, depth and cardinalities of subposets. In particular we study convexity in posets and similarly pre-images of intervals in chains. The problem of extending a map defined on a subposet to the whole poset is discussed.

We investigate positive correlation inequalities, having implications for the complexity of sorting algorithms. These express monotonicity properties for probabilities concerning sets of relations in posets. New proofs are given for existing inequalities and we obtain corresponding negative correlations, along with a generalization of the xyz inequality. The proofs involve inequalities in distributive lattices, some of which arose in physics. A characterization is given for posets satisfying necessary conditions for correlation properties under linear extensions.

A log concavity type inequality is proved for the number of strict or non-strict order-preserving maps of an element. We define an explicit injection whereas the bijective case is proved in the literature using inequalities from the theory of mixed volumes.

These results motivate a further group of such inequalities. But now we count numbers of strict or non-strict order-preserving maps of subposets to varying heights in the chain.

Lastly we consider the computational cost of producing certain posets which can be associated with classical sorting and selection problems. A lower bound technique is derived for this complexity, incorporating either a new distributive lattice inequality, or the log concavity inequalities.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics Q Science > QC Physics
Library of Congress Subject Headings (LCSH):	Monotonic functions -- Research, Partially ordered sets -- Research, Computational complexity, Finite element method
Official Date:	December 1984
Dates:	Date Event December 1984 Submitted
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Paterson, Michael S.
Sponsors:	Science and Engineering Research Council (Great Britain)
Extent:	iii, 174 leaves : illustrations
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads