ISSN:
1572-9273
Keywords:
06A05
;
Ordered sets
;
linear extensions
;
super greedy dimensions
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A linear extension [x 1〈x2〈...〈xt] of a finite ordered set P=(P, 〈) is super greedy if it can be obtained using the following procedure: Choose x 1 to be a minimal element of P; suppose x 1,...,x i have been chosen; define p(x) to be the largest j≤i such that x j〈x if such a j exists and 0 otherwise; choose x i+1 to be a minimal element of P-{ x 1,...,x i} which maximizes p. Every finite ordered set P can be represented as the intersection of a family of super greedy linear extensions, called a super greedy realizer of P. The super greedy dimension of P is the minimum cardinality of a super greedy realizer of P. Best possible upper bounds for the super greedy dimension of P are derived in terms of |P-A| and width (P-A), where A is a maximal antichain.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00337892
Permalink
