Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x₁<x₂<...<x_m] of an ordered set P on m points arises from the simple algorithm: For each i with 0≤i<m, choose x_i+1 as a minimal element of P-{x_j:j≤i}. A linear extension is said to be greedy, if we also require that x_i+1 covers x_i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P-A|≥2, we show that the greedy dimension of P does not exceed |P-A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|≥4. If the width of P-A is n and n≥2, we show that the greedy dimension of P does not exceed n²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2 n-1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.