Antimatroid - Examples

Examples

• A chain antimatroid has as its formal language the prefixes of a single word, and as its feasible sets the sets of symbols in these prefixes. For instance the chain antimatroid defined by the word "abcd" has as its formal language the strings {ε, "a", "ab", "abc", "abcd"} and as its feasible sets the sets Ø, {a}, {a,b}, {a,b,c}, and {a,b,c,d}.

• A poset antimatroid has as its feasible sets the lower sets of a finite partially ordered set. By Birkhoff's representation theorem for distributive lattices, the feasible sets in a poset antimatroid (ordered by set inclusion) form a distributive lattice, and any distributive lattice can be formed in this way. Thus, antimatroids can be seen as generalizations of distributive lattices. A chain antimatroid is the special case of a poset antimatroid for a total order.

• A shelling sequence of a finite set U of points in the Euclidean plane or a higher dimensional Euclidean space is an ordering on the points such that, for each point p, there is a line (in the Euclidean plane, or a hyperplane in a Euclidean space) that separates p from all later points in the sequence. Equivalently, p must be a vertex of the convex hull of it and all later points. The partial shelling sequences of a point set form an antimatroid, called a shelling antimatroid. The feasible sets of the shelling antimatroid are the intersections of U with the complement of a convex set.

• A perfect elimination ordering of a chordal graph is an ordering of its vertices such that, for each vertex v, the neighbors of v that occur later than v in the ordering form a clique. The prefixes of perfect elimination orderings of a chordal graph form an antimatroid.