In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, 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

Cryptomorphism

In mathematics, two objects, especially systems of axioms or semantics for them, are called cryptomorphic if they are equivalent but not obviously equivalent...

, either as a set system modeling the possible states of such a process, or as a formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

 modeling the different sequences in which elements may be included.
Dilworth

Robert P. Dilworth

Robert Palmer Dilworth was an American mathematician. His primary research area was lattice theory; his biography at the MacTutor History of Mathematics archive states "it would not be an exaggeration to say that he was one of the main factors in the subject moving from being merely a tool of...

 (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory

Lattice (order)

In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

, and they have been frequently rediscovered in other contexts; see Korte et al. (1991) for a comprehensive survey of antimatroid theory with many additional references.

The axioms defining antimatroids as set systems have some similarity to those of matroids, but whereas matroids can be defined by an exchange axiom (e.g., the basis exchange, or independent set exchange axioms), antimatroids can be defined instead by an anti-exchange axiom, from which their name derives.
Antimatroids can be viewed as a special case of either greedoid

Greedoid

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms...

s or semimodular lattice

Semimodular lattice

In the branch of mathematics known as order theory, a semimodular lattice, is a lattice that satisfies the following condition:Semimodular law: a ∧ b  ...

s, and as a generalization of partial orders and distributive lattice

Distributive lattice

In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...

s. Antimatroids are also complementary

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 to convex geometries, a combinatorial abstraction of convex set

Convex set

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

s in geometry

Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

.

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 F of sets, called feasible sets, with the following two properties:

• The union
  Union (set theory)
  In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
  
   of any two feasible sets is also feasible. That is, F is closed
  Closure (mathematics)
  In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
  
   under unions.
• If S is a nonempty feasible set, then there exists some x in S such that S \ {x} (the set formed by removing x from S) is also feasible. That is, F is an accessible set system.

Antimatroids also have an equivalent definition as a formal language

Formal language

A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

, that is, as a set of strings

String (computer science)

In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

 defined from a finite alphabet of symbol

Symbol

A symbol is something which represents an idea, a physical entity or a process but is distinct from it. The purpose of a symbol is to communicate meaning. For example, a red octagon may be a symbol for "STOP". On a map, a picture of a tent might represent a campsite. Numerals are symbols for...

s. A language L defining an antimatroid must satisfy the following properties:

• Every symbol of the alphabet occurs in at least one word of L.
• Each word of L contains at most one copy of any symbol.
• Every prefix
  Prefix
  A prefix is an affix which is placed before the root of a word. Particularly in the study of languages,a prefix is also called a preformative, because it alters the form of the words to which it is affixed.Examples of prefixes:...
  
   of a string in L is also in L.
• If s and t are strings in L, and s contains at least one symbol that is not in t, then there is a symbol x in s such that tx is another string in L.

If L is an antimatroid defined as a formal language, then the sets of symbols in strings of L form an accessible union-closed set system. In the other direction, if F is an accessible union-closed set system, and L is the language of strings s with the property that the set of symbols in each prefix of s is feasible, then L defines an antimatroid. Thus, these two definitions lead to mathematically equivalent classes of objects.

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
  Partially ordered set
  In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
  
  . By Birkhoff's representation theorem
  Birkhoff's representation theorem
  In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...
  
   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
  Total order
  In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
  
  .

• A shelling sequence of a finite set U of points in the Euclidean plane or a higher dimensional Euclidean space
  Euclidean space
  In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
  
   is an ordering on the points such that, for each point p, there is a line
  Line (geometry)
  The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...
  
   (in the Euclidean plane, or a hyperplane
  Hyperplane
  A hyperplane is a concept in geometry. It is a generalization of the plane into a different number of dimensions.A hyperplane of an n-dimensional space is a flat subset with dimension n − 1...
  
   in a Euclidean space) that separates p from all later points in the sequence. Equivalently, p must be a vertex of the convex hull
  Convex hull
  In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
  
   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
  Complement (set theory)
  In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
  
   of a convex set.

• A perfect elimination ordering of a chordal graph
  Chordal graph
  In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
  
   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
  Clique (graph theory)
  In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
  
  . The prefixes of perfect elimination orderings of a chordal graph form an antimatroid.

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 S is any feasible set of the antimatroid, an element x that can be removed from a S to form another feasible set is called an endpoint of S, 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 S in the antimatroid, and every element x of S, one may find a path subset of S for which x is an endpoint: to do so, remove one at a time elements other than x until no such removal leaves a feasible subset. Therefore, each feasible set in an antimatroid is the union of its path subsets. If S is not a path, each subset in this union is a proper subset of S. But, if S is itself a path with endpoint x, each proper subset of S that belongs to the antimatroid excludes x. Therefore, the paths of an antimatroid are exactly the sets that do not equal the unions of their proper subsets in the antimatroid. Equivalently, a given family of sets P forms the set of paths of an antimatroid if and only if, for each S in P, the union of subsets of S in P has one fewer element than S itself. If so, F itself is the family of unions of subsets of P.

In the formal language formalization of an antimatroid we may also identify a subset of words that determine the whole language, the basic words.
The longest strings in L are called basic words; each basic word forms a permutation of the whole alphabet. For instance, the basic words of a poset antimatroid are the linear extension

Linear extension

In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...

s of the given partial order. If B is the set of basic words, L can be defined from B as the set of prefixes of words in B. It is often convenient to define antimatroids from basic words in this way, but it is not straightforward to write an axiomatic definition of antimatroids in terms of their basic words.

Convex geometries

If F is the set system defining an antimatroid, with U equal to the union of the sets in F, then the family of sets
complementary

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 to the sets in F is sometimes called a convex geometry, and the sets in G are called convex sets. For instance, in a shelling antimatroid, the convex sets are intersections of U with convex subsets of the Euclidean space into which U is embedded.

Complementarily to the properties of set systems that define antimatroids, the set system defining a convex geometry should be closed under intersections, and for any set S in G 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 G.

A convex geometry can also be defined in terms of a closure operator

Closure operator

In mathematics, a closure operator on a set S is a function cl: P → P from the power set of S to itself which satisfies the following conditions for all sets X,Y ⊆ S....

 τ that maps any subset of U to its minimal closed superset. To be a closure operator, τ should have the following properties:

• τ(Ø) = Ø: the closure of the empty set
  Empty set
  In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
  
   is empty.
• Any set S is a subset of τ(S).
• If S is a subset of T, then τ(S) must be a subset of τ(T).
• For any set S, τ(S) = τ(τ(S)).

The family of closed sets resulting from a closure operation of this type is necessarily closed under intersections. The closure operators that define convex geometries also satisfy an additional anti-exchange axiom:

• If neither y nor z belong to τ(S), but z belongs to τ(S ∪ {y}), then y does not belong to τ(S ∪ {z}).

A closure operation satisfying this axiom is called an anti-exchange closure. If S is a closed set in an anti-exchange closure, then the anti-exchange axiom determines a partial order on the elements not belonging to S, where x ≤ y in the partial order when x belongs to τ(S ∪ {y}). If x is a minimal element of this partial order, then S ∪ {x} 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 x 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.

Join-distributive lattices

Any two sets in 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 sets of an antimatroid, partially ordered by set inclusion, form a lattice

Lattice (order)

In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

. 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 lattice

Distributive lattice

In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...

s, and can be characterized in several different ways.

• The description originally considered by concerns meet-irreducible elements of the lattice. For each element x of an antimatroid, there exists a unique maximal feasible set S_x that does not contain x (S_x is the union of all feasible sets not containing x). S_x is meet-irreducible, meaning that it is not the meet of any two larger lattice elements: any larger feasible set, and any intersection of larger feasible sets, contains x and so does not equal S_x. Any element of any lattice can be decomposed as a meet of meet-irreducible sets, often in multiple ways, but in the lattice corresponding to an antimatroid each element T has a unique minimal family of meet-irreducible sets S_x whose meet is T; this family consists of the sets S_x such that T ∪ {x} belongs to the antimatroid. That is, the lattice has unique meet-irreducible decompositions.

• A second characterization concerns the intervals in the lattice, the sublattices defined by a pair of lattice elements x ≤ y and consisting of all lattice elements z with x ≤ z ≤ y. An interval is atomistic if every element in it is the join of atoms (the 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.

• Thirdly, the lattices arising from antimatroids are semimodular lattice
  Semimodular lattice
  In the branch of mathematics known as order theory, a semimodular lattice, is a lattice that satisfies the following condition:Semimodular law: a ∧ b  ...
  
  s, lattices that satisfy the upper semimodular law that for any two elements x and y, if y covers x ∧ y then x ∨ y covers x. Translating this condition into the sets of an antimatroid, if a set Y has only one element not belonging to X then that one element may be added to X to form another set in the antimatroid. Additionally, the lattice of an antimatroid has the meet-semidistributive property: for all lattice elements x, y, and z, if x ∧ y and x ∧ z are both equal then they also equal x ∧ (y ∨ z). A semimodular and meet-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 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

Graded poset

In mathematics, in the branch of combinatorics, a graded poset, sometimes called a ranked poset , is a partially ordered set P equipped with a rank function ρ from P to N compatible with the ordering such that whenever y covers x, then...

 (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 x of the lattice consists of the set of meet-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) may be viewed as an analogue of Birkhoff's representation theorem

Birkhoff's representation theorem

In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets...

 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

Coxeter group

In mathematics, a Coxeter group, named after H.S.M. Coxeter, is an abstract group that admits a formal description in terms of mirror symmetries. Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; the symmetry groups of regular polyhedra are an example...

, studied antimatroids which are also supersolvable lattices. A supersolvable antimatroid is defined by a totally ordered

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

 collection of elements, and a family of sets

Family of sets

In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets...

 of these elements. The family must include the empty set. Additionally, it must have the property that if two sets A and B belong to the family, the set-theoretic difference B \ A is nonempty, and x is the smallest element of B \ A, then A ∪ {x} 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 A and B are two antimatroids, both described as a family of sets, and if the maximal sets in A and B are equal, we can form another antimatroid, the join of A and B, as follows:


Note that 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 that have a given maximal set forms a semilattice

Semilattice

In mathematics, a join-semilattice is a partially ordered set which has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset...

 with this join operation.

Joins are closely related to a closure operation that maps formal languages to antimatroids, where the closure of a language L is the intersection of all antimatroids containing L as a sublanguage. This closure has as its feasible sets the unions of prefixes of strings in L. In terms of this closure operation, the join is the closure of the union of the languages of A and B.

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 minimum number of chain antimatroids (or equivalently the minimum number of basic words) in such a representation. If F is a family of chain antimatroids whose basic words all belong to A, then F generates A if and only if the feasible sets of F include all paths of A. The paths of A belonging to a single chain antimatroid must form a chain in the path poset of A, so the convex dimension of an antimatroid equals the minimum number of chains needed to cover the path poset, which by Dilworth's theorem

Dilworth's theorem

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains...

 equals the width of the path poset.

If one has a representation of an antimatroid as the closure of a set of d basic words, then this representation can be used to map the feasible sets of the antimatroid into d-dimensional Euclidean space: assign one coordinate per basic word w, and make the coordinate value of a feasible set S be the length of the longest prefix of w that is a subset of S. With this embedding, S is a subset of T if and only if the coordinates for S are all less than or equal to the corresponding coordinates of T. Therefore, the order dimension

Order dimension

In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....

 of the inclusion ordering of the feasible sets is at most equal to the convex dimension of the antimatroid. However, in general these two dimensions may be very different: there exist antimatroids with order dimension three but with arbitrarily large convex dimension.

Enumeration

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 is

1, 3, 22, 485, 59386, ... .

Applications

Both the precedence and release time constraints in the standard notation for theoretic scheduling problems

Notation for theoretic scheduling problems

A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan. It consists of three fields: α, β and γ.Each field may be a comma separated list of words...

 may be modeled by antimatroids. use antimatroids to generalize a greedy algorithm

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

 of Eugene Lawler

Eugene Lawler

Eugene Leighton Lawler was an American computer scientist, a professor of computer science at the University of California, Berkeley.-Academic life:...

 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.

use antimatroids to model the ordering of events in discrete event simulation

Discrete Event Simulation

In discrete-event simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system...

 systems.

uses antimatroids to model progress towards a goal in artificial intelligence

Artificial intelligence

Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

 planning

Automated planning and scheduling

Automated planning and scheduling is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles. Unlike classical control and classification problems, the solutions are...

 problems.

In mathematical psychology

Mathematical psychology

Mathematical psychology is an approach to psychological research that is based on mathematical modeling of perceptual, cognitive and motor processes, and on the establishment of law-like rules that relate quantifiable stimulus characteristics with quantifiable behavior...

, antimatroids have been used to describe feasible states of knowledge

Knowledge space

In mathematical psychology, a knowledge space is a combinatorial structure describing the possible states of knowledge of a human learner.To form a knowledge space, one models a domain of knowledge as a set of concepts, and a feasible state of knowledge as a subset of that set containing the...

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. The axioms defining an antimatroid may be phrased informally as stating that learning one concept can never prevent the learner from learning another concept, and that any feasible state of knowledge can be reached by learning a single concept at a time. The task of a knowledge assessment system is to infer the set of concepts known by a given learner by analyzing his or her responses to a small and well-chosen set of problems. In this context antimatroids have also been called "learning spaces" and "well-graded knowledge spaces".