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.See for a comprehensive survey of antimatroid theory with many additional references. 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.Two early references are and ; Jamison was the first to use the term "antimatroid". surveys the history of rediscovery of antimatroids.
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 of finite sets, called feasible sets, with the following two properties:See e.g. , Definition 2.1 and Proposition 2.3, p. 2. The union of any two feasible sets is also feasible. That is, is closed under unions. If is a nonempty feasible set, then contains an element for which (the set formed by removing from ) is also feasible. That is, is an accessible set system.
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 defining an antimatroid must satisfy the following properties: Every symbol of the alphabet occurs in at least one word of . Each word of contains at most one copy of each symbol. A language with this property is called normal. Every prefix of a word in is also in . A language with this property is called hereditary. If and are words in , and contains at least one symbol that is not in , then there is a symbol in such that the concatenation is another word in .
The equivalence of these two forms of definition can be seen as follows. If is an antimatroid defined as a formal language, then the sets of symbols in words of 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 , the language of normal strings whose prefixes all have sets of symbols belonging to 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:
Chain 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 has as its formal language the set of strings (where denotes the empty string) and as its family of feasible sets the family Poset antimatroids 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. Shelling antimatroids A shelling sequence of a finite set 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 with the complement of a convex set. Perfect elimination A perfect elimination ordering of a chordal graph is an ordering of its vertices such that, for each vertex , the neighbors of that occur later than in the ordering form a clique. The prefixes of perfect elimination orderings of a chordal graph form an antimatroid. describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by . use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph. Chip-firing games 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 is at least as large as the number of edges out of , it is possible to fire , moving one chip to each neighboring vertex. The event that fires for the th time can only happen if it has already fired times and accumulated total chips. These conditions do not depend on the ordering of previous firings, and remain true until fires, so any given graph and initial placement of chips for which the system terminates defines an antimatroid on the pairs . 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 is any feasible set of the antimatroid, an element that can be removed from to form another feasible set is called an endpoint of , 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 in the antimatroid, and every element of , one may find a path subset of for which is an endpoint: to do so, remove one at a time elements other than until no such removal leaves a feasible subset. Therefore, each feasible set in an antimatroid is the union of its path subsets. If is not a path, each subset in this union is a proper subset of . But, if is itself a path with endpoint , each proper subset of that belongs to the antimatroid excludes . 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 forms the family of paths of an antimatroid if and only if, for each in , the union of subsets of in has one fewer element than itself.See , Theorem 3.13, p. 32, which defines paths as rooted sets, sets with a distinguished element, and states an equivalent characterization on the families of rooted sets that form the paths of antimatroids. If so, itself is the family of unions of subsets of .
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 is the set of basic words, can be defined from as the set of prefixes of words in .See , p. 22: "any word in an antimatroid can be extended to a basic word".
Convex geometries
If is the set system defining an antimatroid, with equal to the union of the sets in , then the family of sets
complementary to the sets in is sometimes called a convex geometry and the sets in 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 in that is not equal to there must be an element not in that can be added to to form another set in .
A convex geometry can also be defined in terms of a closure operator that maps any subset of to its minimal closed superset. To be a closure operator, should have the following properties: : the closure of the empty set is empty. For every subset of , is a subset of and . Whenever , is a subset of . 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: If is a subset of , and and are distinct elements of that do not belong to , but does belong to , then does not belong to . A closure operation satisfying this axiom is called an anti-exchange closure. If is a closed set in an anti-exchange closure, then the anti-exchange axiom determines a partial order on the elements not belonging to , where in the partial order when belongs to . If is a minimal element of this partial order, then 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 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.