antimatroid
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an antimatroid is a
formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A form ...
that describes processes in which a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 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, set f ...
modeling the possible states of such a process, or as a
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
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 A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...
, and they have been frequently rediscovered in other contexts. The axioms defining antimatroids as set systems are very similar to those of
matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s, 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
greedoid In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Hassler Whitney, Whitney in 1935 to study planar graphs and was later used by Jack Edmonds, Edmonds to characterize a ...
s and of
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''  <:  ''a''   implies   ''b'' & ...
s, and as a generalization of
partial order In mathematics, especially order theory, a partially ordered set (also poset) 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 ...
s and of
distributive lattice In mathematics, a distributive lattice is a lattice in 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 uni ...
s. Antimatroids are equivalent, by complementation, to convex geometries, a combinatorial abstraction of
convex set In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
s in
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
. Antimatroids have been applied to model precedence constraints in scheduling problems, potential event sequences in simulations, task planning in
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
, and the states of knowledge of human learners.


Definitions

An antimatroid can be defined as a finite family \mathcal of finite sets, called ''feasible sets'', with the following two properties: * The
union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...
of any two feasible sets is also feasible. That is, \mathcal is closed under unions. * If S is a nonempty feasible set, then S contains an element x for which S\setminus\ (the set formed by removing x from S) is also feasible. That is, \mathcal is an accessible set system. Antimatroids also have an equivalent definition as a
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
, that is, as a set of
strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...
defined from a finite alphabet of
symbol A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise very different conc ...
s. A string that belongs to this set is called a ''word'' of the language. A language \mathcal defining an antimatroid must satisfy the following properties: * Every symbol of the alphabet occurs in at least one word of \mathcal. * Each word of \mathcal contains at most one copy of each symbol. A language with this property is called ''normal''. * Every
prefix A prefix is an affix which is placed before the Word stem, stem of a word. Adding it to the beginning of one word changes it into another word. For example, when the prefix ''un-'' is added to the word ''happy'', it creates the word ''unhappy'' ...
of a word in \mathcal is also in \mathcal. A language with this property is called ''hereditary''. * If S and T are words in \mathcal, and S contains at least one symbol that is not in T, then there is a symbol x in S such that the
concatenation In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
Tx is another word in \mathcal. The equivalence of these two forms of definition can be seen as follows. If \mathcal is an antimatroid defined as a formal language, then the sets of symbols in words of \mathcal 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 \mathcal, the language of normal strings whose prefixes all have sets of symbols belonging to \mathcal 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 abcd has as its formal language the set of strings \ (where \varepsilon denotes the
empty string In formal language theory, the empty string, or empty word, is the unique string of length zero. Formal theory Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
) and as its family of feasible sets the family \bigl\. ;Poset antimatroids :The
lower set In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
s of a finite
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
form an antimatroid, with the full-length words of the antimatroid forming the
linear extension In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extens ...
s of the partial order. By
Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...
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 In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
. ;Shelling antimatroids :A ''shelling sequence'' of a finite set U of points in the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
or a higher-dimensional
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
is formed by repeatedly removing vertices of the
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
. The feasible sets of the antimatroid formed by these sequences are the
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
s of U with the
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
of a convex set. Every antimatroid is isomorphic to a shelling antimatroid of points in a sufficiently high-dimensional space. ;Perfect elimination :A ''
perfect elimination ordering In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
'' of a
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...
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 A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
. The prefixes of perfect elimination orderings of a chordal graph form an antimatroid. ;Chip-firing games :
Chip-firing game The chip-firing game is a one-player game on a graph which was invented around 1983 and since has become an important part of the study of structural combinatorics. Each vertex has the number of "chips" indicated by its state variable. On each ...
s such as the
abelian sandpile model The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, ...
are defined by a
directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
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 v, it is possible to ''fire'' v, moving one chip to each neighboring vertex. The event that v fires for the ith time can only happen if it has already fired i-1 times and accumulated i\cdot\deg(v) total chips. These conditions do not depend on the ordering of 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 (v,i). 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 S is any feasible set of the antimatroid, an element x that can be removed from 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 In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
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 feasible sets that do not equal the unions of their proper feasible subsets. Equivalently, a given family of sets \mathcal forms the family of paths of an antimatroid if and only if, for each S in \mathcal, the union of subsets of S in \mathcal has one fewer element than S itself. If so, \mathcal itself is the family of unions of subsets of \mathcal. 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 B is the set of basic words, \mathcal can be defined from B as the set of prefixes of words in B.


Convex geometries

If \mathcal is the set system defining an antimatroid, with U equal to the union of the sets in \mathcal, then the family of sets \mathcal = \
complementary A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...
to the sets in \mathcal is sometimes called a convex geometry and the sets in \mathcal 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 S in \mathcal 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 \mathcal. A convex geometry can also be defined in terms of a
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are dete ...
\tau that maps any subset of U to its minimal closed superset. To be a closure operator, \tau should have the following properties: * \tau(\emptyset)=\emptyset: the closure of the
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
is empty. * For every subset S of U, S is a subset of \tau(S) and \tau(S)=\tau\bigl(\tau(S)\bigr). * Whenever S\subset T\subset U, \tau(S) is a subset of \tau(T). 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 S is a subset of U, and y and z are distinct elements of U that do not belong to \tau(S), but z does belong to \tau(S\cup\), then y does not belong to \tau(S\cup\). 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\le y in the partial order when x belongs to \tau(S\cup\). If x is a minimal element of this partial order, then S\cup\ 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. The
undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
s in which the convex sets (subsets of vertices that contain all
shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...
s between vertices in the subset) form a convex geometry are exactly the
Ptolemaic graph In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs tha ...
s.


Join-distributive lattices

Every two feasible sets of an antimatroid have a unique
least upper bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest low ...
(their union) and a unique
greatest lower bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
(the union of the sets in the antimatroid that are contained in both of them). Therefore, the feasible sets of an antimatroid,
partially ordered In mathematics, especially order theory, a partially ordered set (also poset) 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 r ...
by set inclusion, form a
lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...
. 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 chain This is a glossary of some terms used in various branches of mathematics that are related to the fields of Order theory, order, Lattice (order), lattice, and domain theory. Note that there is a structured list of order topics available as well. Ot ...
s in the lattice. The lattices that arise from antimatroids in this way generalize the finite
distributive lattice In mathematics, a distributive lattice is a lattice in 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 uni ...
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 can be constructed as the union of all feasible sets not containing x. This set S_x is automatically meet-irreducible, meaning that it is not the meet of any two larger lattice elements. This is true because every feasible superset of S_x contains x, and the same is therefore also true of every intersection of feasible supersets. Every element of an arbitrary 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 whose meet is T; this family consists of the sets S_x for the elements x such that T\cup\ is feasible. 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\le y consisting of all lattice elements z with x\le z\le 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 In the branch of mathematics known as order theory, a semimodular lattice, is a lattice that satisfies the following condition: ;Semimodular law: ''a'' ∧ ''b''  <:  ''a''   implies   ''b'' & ...
s, lattices that satisfy the ''upper semimodular law'' that for every two elements x and y, if y covers x\wedge y then x\vee y covers x. Translating this condition into the feasible sets of an antimatroid, if a feasible set Y has only one element not belonging to another feasible set 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\wedge y and x\wedge z equal each other then they also both equal x\wedge (y\vee 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 (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 :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...
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 In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean refl ...
, studied antimatroids which are also supersolvable lattices. A supersolvable antimatroid is defined by a
totally ordered In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
collection of elements, and a
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, set fam ...
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, if the set-theoretic difference B\setminus A is nonempty, and if x is the smallest element of B\setminus A, then A\cup\ 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 \mathcal and \mathcal are two antimatroids, both described as a family of sets over the same universe of elements, then another antimatroid, the ''join'' of \mathcal and \mathcal, can be formed as follows: \mathcal\vee\mathcal = \. 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 In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
with this join operation. Joins are closely related to a closure operation that maps formal languages to antimatroids, where the closure of a language \mathcal is the intersection of all antimatroids containing \mathcal as a sublanguage. This closure has as its feasible sets the unions of prefixes of strings in \mathcal. In terms of this closure operation, the join is the closure of the union of the languages of \mathcal and \mathcal. 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 \mathcal is the minimum number of chain antimatroids (or equivalently the minimum number of basic words) in such a representation. If \mathfrak is a family of chain antimatroids whose basic words all belong to \mathcal, then \mathfrak generates \mathcal if and only if the feasible sets of \mathfrak include all paths of \mathcal. The paths of \mathcal belonging to a single chain antimatroid must form a
chain A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A c ...
in the path poset of \mathcal, so the convex dimension of an antimatroid equals the minimum number of chains needed to cover the path poset, which by
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. It is named for the mathematician . ...
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 to points in 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 another feasible set 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 In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller d ...
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, 133059751, \dots\, .


Applications

Both the precedence and release time constraints in the standard
notation for theoretic scheduling problems Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of ''jobs'' (also called ''processes'' or ''tasks'') and a list of ''machines'' (also called ''processors'' or ''workers''). The ...
may be modeled by antimatroids. use antimatroids to generalize a
greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
of
Eugene Lawler Eugene Leighton (Gene) Lawler (1933 – September 2, 1994) was an American computer scientist and a professor of computer science at the University of California, Berkeley... Reprinted in . Academic life Lawler came to Harvard as a graduate st ...
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 A discrete-event simulation (DES) models the operation of a system as a ( discrete) sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in the system. Between consecutive events, no change in t ...
systems. uses antimatroids to model progress towards a goal in
artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...
planning Planning is the process of thinking regarding the activities required to achieve a desired goal. Planning is based on foresight, the fundamental capacity for mental time travel. The evolution of forethought, the capacity to think ahead, is consi ...
problems. In
Optimality Theory In linguistics, Optimality Theory (frequently abbreviated OT) is a linguistic model proposing that the observed forms of language arise from the optimal satisfaction of conflicting constraints. OT differs from other approaches to phonological ...
, a mathematical model for the development of
natural language In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
based on optimization under constraints, grammars are logically equivalent to antimatroids. In
mathematical psychology Mathematical psychology is an approach to psychological research that is based on mathematical modeling of perceptual, thought, cognitive and motor processes, and on the establishment of law-like rules that relate quantifiable stimulus characte ...
, 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. 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".


Notes


References

*. *. * * * *. * *. *. *. *. *. Partially adapted as Chapters 13 and 14 of . *. *. *. *. *. * * *. *. *. *. {{refend Algebraic combinatorics Lattice theory Convex geometry Formal languages Families of sets Matroid theory Discrete mathematics