Lecture
In mathematics an antimatroid — is a formal system describing processes in which a set is created by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are usually 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 various sequences in which the elements may be included. Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they were often rediscovered in other contexts.
The axioms defining antimatroids as set systems are very similar to the axioms of matroids, but whereas matroids are defined by the exchange axiom, antimatroids are defined by the anti-exchange axiom, from which their name is derived. Antimatroids can be regarded as a special case of greedoids and of semimodular lattices, and also as a generalization of partial orders and 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 sequences of events in simulations, task planning in artificial intelligence, and the states of knowledge of human learners.
Three representations of an antimatroid: the inclusion order on its family of feasible sets, the formal language, and the corresponding path of a partially ordered set.
An antimatroid can be defined as a finite family 
of finite sets, called feasible sets, with the following two properties:
is closed under unions.
— is a non-empty 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 over 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:
.contains no more than one copy of each symbol. A language with this property is called normal. [ is also in . A language with this property is called hereditary. and 
are words in , and contains at least one symbol that is not in , then there is a symbol x in S 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 the words of form an accessible set system closed under union. It is accessible by the hereditary property of the strings, and it can be shown to be closed under union by repeated application of the string-concatenation property. In the other direction, from an accessible set system closed under union , the language of normal strings all of whose prefixes have symbol sets belonging to meets the requirements of a formal language to be an antimatroid. These two transformations are inverses of each other: transforming a formal language into a family of sets and back, or vice versa, produces the same system. Thus, these two definitions lead to mathematically equivalent classes of objects.
A sequence of hulls of a planar set of points. The line segments show the edges of the convex hulls after some points are removed.
Examples of antimatroids are the following systems:
Chain antimatroids
The prefixes of a single string and the sets of symbols in these prefixes form an antimatroid. For example, 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 complete 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 regarded as generalizations of distributive lattices. A chain antimatroid is a 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 in 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 v 
, the neighbors of v that occur later than in the ordering form a clique. The prefixes of perfect elimination orderings of a chordal graph form an antimatroid.
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 v is at least as large as the number of edges out of , one can fire , moving one chip to each neighboring vertex. The event that fires for the 
th time can occur only if it has already fired 
times and accumulated ⋅ 
chips in total. These conditions do not depend on the order of the previous firings and remain true until v 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 firings of each vertex and the final stable state of the system do not depend on the firing order.
In the set-theoretic axiomatization of an antimatroid there are certain special sets, called paths, that determine the entire 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 having only one endpoint is called a path of the antimatroid. The family of paths can be partially ordered by set inclusion, forming the partially ordered set of paths of the antimatroid.
For each feasible set in the antimatroid, and each element x of , one can find a subset of the paths of for which is an endpoint: to do this, remove one element at a time, except x , until no such removal leaves a feasible subset. Thus, every feasible set in the antimatroid is a union of its path subsets. If is not a path, each subset in this union is a proper subset of . But if S is itself a path with endpoint x , every proper subset of that belongs to the antimatroid excludes x . Thus, the paths of an antimatroid — are exactly the feasible sets that are not equal to unions of their own 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 the subsets of in has one element fewer than itself. If so, is itself 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 .
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 example, in the shelling antimatroid the convex sets are the intersections of the given set of points with convex subsets of Euclidean space. The set system defining a convex geometry must be closed under intersections. For any set S in that is not equal to U there must be an element x not in S that can be added to S to form another set in .
A convex geometry can also be defined in terms of a closure operator τ
that maps any subset of U to its minimal closed superset. To be a closure operator, τmust have the following properties:
: the closure of the empty set is empty.of U , S is a subset of 
and 
.
, is a subset of 
.The family of closed sets obtained as the result of a closure operation of this type is necessarily closed under intersections, but may not be a convex geometry. The closure operators defining convex geometries also satisfy an additional anti-exchange axiom:
is a subset of , and 
and 
are distinct elements of that do not belong to , but z belongs 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 defines a partial order on the elements not belonging to S , where x≤y 
in the partial order when belongs to . If x 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 obtain 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 containing all shortest paths between vertices in the subset) form a convex geometry are exactly the Ptolemaic graphs.
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). Thus, the feasible sets of an antimatroid, partially ordered by set inclusion, form a lattice. Various important features of an antimatroid can be interpreted in terms of lattice theory; for example, the paths of an antimatroid are the join-irreducibles of the corresponding lattice, and the basic words of the antimatroid correspond to the maximal chains in the lattice. The lattices that arise from antimatroids in this way generalize finite distributive lattices and can be characterized in several different ways.
of the antimatroid there is a unique maximal feasible set x 
that does not contain x : S_x can be constructed as the union of all feasible sets not containing . This set is automatically meet-irreducible, meaning that it is not the meet of two larger elements of the lattice. This is true because every feasible superset of contains , and the same therefore holds for any intersection of feasible supersets. Every element of an arbitrary lattice can be decomposed as a meet of meet-irreducible sets, often in several ways, but in the lattice corresponding to an antimatroid each element T has a unique minimal family of meet sets whose intersection is T ; this family consists of the sets S_x for the elements x such that 
is feasible. That is, the lattice has unique meet-irreducible decompositions.consisting of all lattice elements 
. An interval is atomistic if every element in it is a join of atoms (minimal elements above the bottom element x ), and it is Boolean if it is isomorphic to the lattice of all subsets of a finite set. For an antimatroid every interval that is atomistic is also Boolean.and y , if y covers 
then 
covers . Translating this condition into the feasible sets of the antimatroid, if a feasible set Y 
has only one element not belonging to another feasible set 
then that one element can be added to to form another set in the antimatroid. In addition, the lattice of an antimatroid has the meet-semidistributive property: for all lattice elements , and , if and 
are equal to each other, then they are also both equal to 
. A semimodular and semidistributive lattice is called a join-distributive lattice.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 call a lattice with any of these three properties 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. An antimatroid representing a finite join-distributive lattice can be recovered from the lattice: the elements of the antimatroid can be taken as the meet-irreducible elements of the lattice, and the feasible set corresponding to any element x of the lattice consists of the set of irreducible elements y such that y is not greater than or equal to x 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) can be regarded as an analogue of Birkhoff's representation theorem, according to which any finite distributive lattice has a representation as a family of sets closed under unions and intersections.
Motivated by the problem of defining partial orders on the elements of a Coxeter group, Armstrong (2009) studied antimatroids that are also supersolvable lattices. A supersolvable antimatroid is defined by a totally ordered set of elements and a family of sets of these elements. The family must include the empty set. In addition, it must have the property that if two sets A 
and B belong to the family, if the set-theoretic difference 
is non-empty, and if x is the smallest element of , then 
also belongs to this family. As Armstrong notes, any family of sets of this type forms an antimatroid. Armstrong also gives a lattice-theoretic characterization of the antimatroids that this construction can form.
If 
and 
are two antimatroids, both described as families of sets over the same universe of elements, then another antimatroid, the join of and , can be formed as follows: A∨B= 
This is a different operation from 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 closure of a language is the intersection of all antimatroids containing as a sublanguage. This closure has as its feasible sets the unions of prefixes of strings in . In terms of this closure operation, the join is the closure of the union of the languages and . 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 minimal number of chain antimatroids (or, equivalently, the minimal number of basic words) in such a representation. If 
is a family of chain antimatroids all of whose basic words belong to , then generates if and only if the feasible sets of include all paths of . The paths of A belonging to a single chain antimatroid must form a chain in the poset of paths of A , so the convex dimension of an antimatroid equals the minimal number of chains needed to cover the poset of paths, which by Dilworth's theorem equals the width of the poset of paths.
If you have a representation of an antimatroid as the closure of a set of 
basic words, then, simply put, this representation can be used to map the feasible sets of the antimatroid to points of d -dimensional Euclidean space: assign one coordinate to each basic word 
, and make the coordinate value of a feasible set be the length of the longest prefix of that is a subset of . With this embedding, is a subset of another feasible set if and only if the coordinates for are all less than or equal to the corresponding coordinates of . Thus, the order dimension of the inclusion order of the feasible sets does not exceed the convex dimension of the antimatroid. However, in general these two dimensions can differ greatly: there exist antimatroids with order dimension three but with arbitrarily large convex dimension.
The number of possible antimatroids on a set of elements grows rapidly with the number of elements in the set. For sets of one, two, three, etc. elements, the number of distinct antimatroids equals 
Both precedence time constraints and release time constraints in the standard notation for theoretical scheduling problems can be modeled by antimatroids. Boyd and Faigle (1990) use antimatroids to generalize Eugene Lawler's greedy algorithm for optimally solving single-processor scheduling problems with precedence constraints, in which the goal is to minimize the maximum penalty caused by the late scheduling of a task.
Glasserman and Yao (1994) use antimatroids to model the order of events in discrete-event simulation systems.
Parmar (2003) uses antimatroids to model progress toward a goal in artificial-intelligence planning problems.
In optimality theory, a mathematical model of the development of natural language based on optimization under constraints, grammars are logically equivalent to antimatroids.
In mathematical psychology antimatroids have been used to describe the possible states of knowledge of a human learner. Each element of the antimatroid represents a concept that the learner must understand, or a class of problems that he or she could solve correctly, and the sets of elements that form the antimatroid represent the possible sets of concepts that a single person could understand. The axioms defining an antimatroid can be informally stated as follows: learning one concept can never prevent the learner from learning another concept, and any possible state of knowledge can be reached by learning one concept at a time. The task of a knowledge-assessment system is to infer the set of concepts known to a given learner by analyzing his or her answers to a small and well-chosen set of problems. In this context antimatroids are also called «learning spaces» and «well-graded knowledge spaces».
Comments