Antimatroid - Join Operation and Convex Dimension

Join Operation and Convex Dimension

If A and B are two antimatroids, both described as a family of sets, and if the maximal sets in A and B are equal, we can form another antimatroid, the join of A and B, as follows:

Note that this is a different operation than the join considered in the lattice-theoretic characterizations of antimatroids: it combines two antimatroids to form another antimatroid, rather than combining two sets in an antimatroid to form another set. The family of all antimatroids that have a given maximal set forms a semilattice with this join operation.

Joins are closely related to a closure operation that maps formal languages to antimatroids, where the closure of a language L is the intersection of all antimatroids containing L as a sublanguage. This closure has as its feasible sets the unions of prefixes of strings in L. In terms of this closure operation, the join is the closure of the union of the languages of A and B.

Every antimatroid can be represented as a join of a family of chain antimatroids, or equivalently as the closure of a set of basic words; the convex dimension of an antimatroid A is the minimum number of chain antimatroids (or equivalently the minimum number of basic words) in such a representation. If F is a family of chain antimatroids whose basic words all belong to A, then F generates A if and only if the feasible sets of F include all paths of A. The paths of A belonging to a single chain antimatroid must form a chain in the path poset of A, so the convex dimension of an antimatroid equals the minimum number of chains needed to cover the path poset, which by Dilworth's theorem equals the width of the path poset.

If one has a representation of an antimatroid as the closure of a set of d basic words, then this representation can be used to map the feasible sets of the antimatroid into d-dimensional Euclidean space: assign one coordinate per basic word w, and make the coordinate value of a feasible set S be the length of the longest prefix of w that is a subset of S. With this embedding, S is a subset of T if and only if the coordinates for S are all less than or equal to the corresponding coordinates of T. Therefore, the order dimension of the inclusion ordering of the feasible sets is at most equal to the convex dimension of the antimatroid. However, in general these two dimensions may be very different: there exist antimatroids with order dimension three but with arbitrarily large convex dimension.