Antimatroid
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.
[1] 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.
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.
defining an antimatroid must satisfy the following properties:[4] The equivalence of these two forms of definition can be seen as follows.
is an antimatroid defined as a formal language, then the sets of symbols in words of
, the language of normal strings whose prefixes all have sets of symbols belonging to
Thus, these two definitions lead to mathematically equivalent classes of objects.
, and a feasible set that has only one endpoint is called a path of the antimatroid.
The set system defining a convex geometry must be closed under intersections.
[17] A convex geometry can also be defined in terms of a closure operator
Therefore, the complements of the closed sets of any anti-exchange closure form an antimatroid.
[17] 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.
[19] 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).
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.
[21] 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.
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.
Motivated by a problem of defining partial orders on the elements of a Coxeter group, Armstrong (2009) studied antimatroids which are also supersolvable lattices.
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.
The family of all antimatroids over the same universe forms a semilattice with this join operation.
is a family of chain antimatroids whose basic words all belong to
, 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.
basic words, then this representation can be used to map the feasible sets of the antimatroid to points in
-dimensional Euclidean space: assign one coordinate per basic word
Both the precedence and release time constraints in the standard notation for theoretic scheduling problems may be modeled by antimatroids.
Boyd & Faigle (1990) use antimatroids to generalize a greedy algorithm of Eugene Lawler for optimally solving single-processor scheduling problems with precedence constraints in which the goal is to minimize the maximum penalty incurred by the late scheduling of a task.
Parmar (2003) uses antimatroids to model progress towards a goal in artificial intelligence planning problems.
[29] In mathematical psychology, antimatroids have been used to describe feasible states of knowledge of a human learner.
Each element of the antimatroid represents a concept that is to be understood by the learner, or a class of problems that he or she might be able to solve correctly, and the sets of elements that form the antimatroid represent possible sets of concepts that could be understood by a single person.
