Representing an ordered set as the intersection of super greedy linear extensions

Abstract

A linear extension [x ₁<x₂<...<x_t] of a finite ordered set P=(P, <) is super greedy if it can be obtained using the following procedure: Choose x ₁ to be a minimal element of P; suppose x ₁,...,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 ₁,...,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.