Mathematical system of orderings or sets
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included.
Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts.
The axioms defining antimatroids as set systems are very similar to those of matroids, but whereas matroids are defined by an "exchange axiom", antimatroids are defined instead by an "anti-exchange axiom", from which their name derives.
Antimatroids can be viewed as a special case of greedoids and of semimodular lattices, and as a generalization of partial orders and of distributive lattices. 
Antimatroids are equivalent, by complementation, to convex geometries, a combinatorial abstraction of convex sets in geometry.
Antimatroids have been applied to model precedence constraints in scheduling problems, potential event sequences in simulations, task planning in artificial intelligence, and the states of knowledge of human learners.
Definitions.
An antimatroid can be defined as a finite family formula_1 of finite sets, called "feasible sets", with the following two properties:
Antimatroids also have an equivalent definition as a formal language, that is, as a set of strings defined from a finite alphabet of symbols. A string that belongs to this set is called a "word" of the language. A language formula_10 defining an antimatroid must satisfy the following properties:
The equivalence of these two forms of definition can be seen as follows. If formula_10 is an antimatroid defined as a formal language, then the sets of symbols in words of formula_10 form an accessible union-closed set system. It is accessible by the hereditary property of strings, and it can be shown to be union-closed by repeated application of the concatenation property of strings. In the other direction, from an accessible union-closed set system formula_1, the language of normal strings whose prefixes all have sets of symbols belonging to formula_1 meets the requirements for a formal language to be an antimatroid. These two transformations are the inverses of each other: transforming a formal language into a set family and back, or vice versa, produces the same system. Thus, these two definitions lead to mathematically equivalent classes of objects.
Examples.
The following systems provide examples of antimatroids:
The prefixes of a single string, and the sets of symbols in these prefixes, form an antimatroid. For instance the chain antimatroid defined by the string formula_28 has as its formal language the set of strings formula_29 (where formula_30 denotes the empty string) and as its family of feasible sets the family formula_31
The lower sets of a finite partially ordered set form an antimatroid, with the full-length words of the antimatroid forming the linear extensions of the partial order. By Birkhoff's representation theorem for distributive lattices, the feasible sets in a poset antimatroid (ordered by set inclusion) form a distributive lattice, and all distributive lattices 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 formula_32 of points in the Euclidean plane or a higher-dimensional Euclidean space is formed by repeatedly removing vertices of the convex hull. The feasible sets of the antimatroid formed by these sequences are the intersections of formula_32 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 formula_34, the neighbors of formula_34 that occur later than formula_34 in the ordering form a clique. The prefixes of perfect elimination orderings of a chordal graph form an antimatroid.
Chip-firing games such as the abelian sandpile model are defined by a directed graph together with a system of "chips" placed on its vertices. Whenever the number of chips on a vertex formula_34 is at least as large as the number of edges out of formula_34, it is possible to "fire" formula_34, moving one chip to each neighboring vertex. The event that formula_34 fires for the formula_41th time can only happen if it has already fired formula_42 times and accumulated formula_43 total chips. These conditions do not depend on the ordering of previous firings, and remain true until formula_34 fires, so any given graph and initial placement of chips for which the system terminates defines an antimatroid on the pairs formula_45. A consequence of the antimatroid property of these systems is that, for a given initial state, the number of times each vertex fires and the eventual stable state of the system do not depend on the firing order.
Paths and basic words.
In the set theoretic axiomatization of an antimatroid there are certain special sets called "paths" that determine the whole antimatroid, in the sense that the sets of the antimatroid are exactly the unions of paths. If formula_3 is any feasible set of the antimatroid, an element formula_5 that can be removed from formula_3 to form another feasible set is called an "endpoint" of formula_3, and a feasible set that has only one endpoint is called a "path" of the antimatroid. The family of paths can be partially ordered by set inclusion, forming the "path poset" of the antimatroid.
For every feasible set formula_3 in the antimatroid, and every element formula_5 of formula_3, one may find a path subset of formula_3 for which formula_5 is an endpoint: to do so, remove one at a time elements other than formula_5 until no such removal leaves a feasible subset. Therefore, each feasible set in an antimatroid is the union of its path subsets. If formula_3 is not a path, each subset in this union is a proper subset of formula_3. But, if formula_3 is itself a path with endpoint formula_5, each proper subset of formula_3 that belongs to the antimatroid excludes formula_5. Therefore, the paths of an antimatroid are exactly the feasible sets that do not equal the unions of their proper feasible subsets. Equivalently, a given family of sets formula_62 forms the family of paths of an antimatroid if and only if, for each formula_3 in formula_62, the union of subsets of formula_3 in formula_62 has one fewer element than formula_3 itself. If so, formula_1 itself is the family of unions of subsets of formula_62.
In the formal language formalization of an antimatroid, the longest strings are called "basic words". Each basic word forms a permutation of the whole alphabet. If formula_70 is the set of basic words, formula_10 can be defined from formula_70 as the set of prefixes of words in formula_70.
Convex geometries.
If formula_1 is the set system defining an antimatroid, with formula_32 equal to the union of the sets in formula_1, then the family of sets
formula_77
complementary to the sets in formula_1 is sometimes called a convex geometry and the sets in formula_79 are called convex sets. For instance, in a shelling antimatroid, the convex sets are intersections of the given point set with convex subsets of Euclidean space. The set system defining a convex geometry must be closed under intersections. For any set formula_3 in formula_79 that is not equal to formula_32 there must be an element formula_5 not in formula_3 that can be added to formula_3 to form another set in formula_79.
A convex geometry can also be defined in terms of a closure operator formula_87 that maps any subset of formula_32 to its minimal closed superset. To be a closure operator, formula_87 should have the following properties:
The family of closed sets resulting from a closure operation of this type is necessarily closed under intersections, but might not be a convex geometry. The closure operators that define convex geometries also satisfy an additional anti-exchange axiom:
A closure operation satisfying this axiom is called an anti-exchange closure. If formula_3 is a closed set in an anti-exchange closure, then the anti-exchange axiom determines a partial order on the elements not belonging to formula_3, where formula_111 in the partial order when formula_5 belongs to formula_106. If formula_5 is a minimal element of this partial order, then formula_115 is closed. That is, the family of closed sets of an anti-exchange closure has the property that for any set other than the universal set there is an element formula_5 that can be added to it to produce another closed set. This property is complementary to the accessibility property of antimatroids, and the fact that intersections of closed sets are closed is complementary to the property that unions of feasible sets in an antimatroid are feasible. Therefore, the complements of the closed sets of any anti-exchange closure form an antimatroid.
The undirected graphs in which the convex sets (subsets of vertices that contain all shortest paths between vertices in the subset) form a convex geometry are exactly the Ptolemaic graphs.
Join-distributive lattices.
Every two feasible sets of an antimatroid have a unique least upper bound (their union) and a unique greatest lower bound (the union of the sets in the antimatroid that are contained in both of them). Therefore, the feasible sets of an antimatroid, partially ordered by set inclusion, form a lattice. Various important features of an antimatroid can be interpreted in lattice-theoretic terms; for instance the paths of an antimatroid are the join-irreducible elements of the corresponding lattice, and the basic words of the antimatroid correspond to maximal chains in the lattice. The lattices that arise from antimatroids in this way generalize the finite distributive lattices, and can be characterized in several different ways.
These three characterizations are equivalent: any lattice with unique meet-irreducible decompositions has boolean atomistic intervals and is join-distributive, any lattice with boolean atomistic intervals has unique meet-irreducible decompositions and is join-distributive, and any join-distributive lattice has unique meet-irreducible decompositions and boolean atomistic intervals. Thus, we may refer to a lattice with any of these three properties as join-distributive. Any antimatroid gives rise to a finite join-distributive lattice, and any finite join-distributive lattice comes from an antimatroid in this way. Another equivalent characterization of finite join-distributive lattices is that they are graded (any two maximal chains have the same length), and the length of a maximal chain equals the number of meet-irreducible elements of the lattice. The antimatroid representing a finite join-distributive lattice can be recovered from the lattice: the elements of the antimatroid can be taken to be the meet-irreducible elements of the lattice, and the feasible set corresponding to any element formula_5 of the lattice consists of the set of meet-irreducible elements formula_101 such that formula_101 is not greater than or equal to formula_5 in the lattice.
This representation of any finite join-distributive lattice as an accessible family of sets closed under unions (that is, as an antimatroid) may be viewed as an analogue of Birkhoff's representation theorem under which any finite distributive lattice has a representation as a family of sets closed under unions and intersections.
Supersolvable antimatroids.
Motivated by a problem of defining partial orders on the elements of a Coxeter group, studied antimatroids which are also supersolvable lattices. A supersolvable antimatroid is defined by a totally ordered collection of elements, and a family of sets of these elements. The family must include the empty set. Additionally, it must have the property that if two sets formula_153 and formula_70 belong to the family, if the set-theoretic difference formula_155 is nonempty, and if formula_5 is the smallest element of formula_155, then formula_158 also belongs to the family. As Armstrong observes, any family of sets of this type forms an antimatroid. Armstrong also provides a lattice-theoretic characterization of the antimatroids that this construction can form.
Join operation and convex dimension.
If formula_159 and formula_160 are two antimatroids, both described as a family of sets over the same universe of elements, then another antimatroid, the "join" of formula_159 and formula_160, can be formed as follows:
formula_163
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 over the same universe forms a semilattice with this join operation.
Joins are closely related to a closure operation that maps formal languages to antimatroids, where the