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. 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, taking a lattice theoretic point of view; 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 are defined by an "exchange axiom", 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 greedoids or semimodular lattices; one characterization of antimatroids is that they are greedoids such that the inclusion ordering on their feasible sets forms a semimodular lattice. [E.g., see Gordon (1997).] Antimatroids generalize partial orders and distributive lattices. Antimatroids are also complementary to convex geometries, a combinatorial abstraction of convex sets in geometry.

Glasserman and Yao (1994) use antimatroids to model the ordering of events in discrete event simulation systems, and Parmar (2003) uses them to model progress towards a goal in artificial intelligence planning problems. In mathematical psychology, antimatroids have been used to describe feasible states of knowledge of a human learner. [See e.g. harvtxt|Doignon|Falmagne|1999, who refer to structures equivalent to antimatroids as "well-graded knowledge spaces".]

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 possible antimatroids is:1, 3, 22, 485, 59386, ... OEIS|id=A119770.

Definitions

An antimatroid can be defined as a finite family "F" of sets, called "feasible sets", with the following two properties:
* The union of any two feasible sets is also feasible. That is, "F" is closed 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.An element "x" that can be removed from a feasible set "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 subset ordering of the paths forms a partially ordered set, called the "path poset" of the antimatroid. Each feasible set in an antimatroid is the union of its path subsets. A 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".

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 language "L" defining an antimatroid must satisfy the following properties:
* Every symbol of the alphabet occurs in at least one word of "L". That is, in the terminology of Korte et al., "L" is "normal".
* No string in "L" contains two copies of the same symbol. That is, in the terminology of Korte et al., "L" is "simple".
* Every prefix of a string in "L" is also in "L". That is, in the terminology of Korte et al., "L" is "hereditary".
* If "s" and "t" are strings in "L", and the set of symbols in "s" is not a subset of the set of symbols in "t", then there is a symbol "x" in "s" such that "tx" is another string in "L".The longest strings in "L" are called "basic words"; each basic word forms a permutation of the whole alphabet. If "B" is the set of basic words, "L" can be defined from "B" as the set of prefixes of words in "B", and it is often convenient to define antimatroids from basic words in this way, but it is not straightforward to write an axiomatic definition antimatroids in terms of their basic words.

If "L" is an antimatroid defined as a formal language, then one can derive from it an accessible union-closed set system "F", where "F" consists of the sets of symbols in strings of "L". 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. [Korte et al., Theorem 1.4.]

Examples

* A "chain antimatroid" is defined by a total order on its elements; the nonempty sets in the antimatroid are all the sets of the form {"y" | "y" ≤ "x"} for some element "x". Thus, a chain antimatroid has exactly one set of each different possible cardinality. A chain antimatroid can also be defined as a formal language, as the set of prefixes of a single basic word.

* A "poset antimatroid" has as its feasible sets the lower sets of a partially ordered set. A chain antimatroid is a special case of a poset antimatroid. By Birkhoff's representation theorem 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. An equivalent way of defining a poset antimatroid as a formal language is that its basic words are the linear extensions of the given partial order. Any antimatroid is the homomorphic image of the poset antimatroid of its path poset. [Korte et al., Corollary 6.2.]

* A "shelling sequence" of a finite set "U" of points in the Euclidean plane or a higher dimensional Euclidean space is an ordering on the points such that, for each point "p", there is a line (in the Euclidean plane, or a hyperplane in a Euclidean space) that separates "p" from all later points in the sequence. Equivalently, "p" must be a vertex of the convex hull of it and all later points. The shelling sequences of a point set form the basic words of an antimatroid, called a "shelling antimatroid". The feasible sets of the shelling antimatroid are the intersections of "U" with the complement of a convex set. As can be seen in the figure, the edges of the convex hulls formed by this shelling process together form a graph that is a pointed pseudotriangulation.

* 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 "v" in the ordering form a clique. The perfect elimination orderings of a chordal graph form the basic words of an antimatroid. [Gordon (1997) describes several results related to antimatroids of this type, but these antimatroids were mentioned earlier e.g. by Korte et al. Chandran et al. (2003) use the connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.]

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:$G\; =\; \{Usetminus\; Smid\; Sin\; F\}$
complementary 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 τ 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 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"}).This axiom can be used to prove the existence of an element "x" that can be added to any non-universal set in the family of convex sets. [Korte et al., Theorem 1.1.]

Join operation and convex dimension

If "A" and "B" are families of sets defining antimatroids over the same set of elements, we can form another antimatroid, the "join" of "A" and "B", as follows:

:$Avee\; B\; =\; \{\; Scup\; T\; mid\; Sin\; A\; wedge\; Tin\; B\; \}.$

The antimatroids over a common set of elements form 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 "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. A family of chain antimatroids whose join is the given antimatroid can be formed from a decomposition of the given antimatroid's path poset into a union of chains, so by Dilworth's theorem the convex dimension of an antimatroid equals the width of its path poset. [Korte et al., Theorem 6.9.]

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 of the inclusion ordering of the feasible sets is at most equal to the convex dimension of the antimatroid. [Korte et al., Corollary 6.10.] However, in general these two dimensions may be very different: there exist antimatroids with order dimension three but with arbitrarily large convex dimension.

Notes

References

*cite journal
author = Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J.
title = Generating and characterizing the perfect elimination orderings of a chordal graph
journal = Theoretical Computer Science
volume = 307
year = 2003
pages = 303–317
url = http://old-www.cis.uoguelph.ca/~sawada/papers/chordal.pdf | doi = 10.1016/S0304-3975(03)00221-4

*cite journal
author = Dilworth, Robert P.
authorlink = Robert P. Dilworth
title = Lattices with unique irreducible decompositions
journal = Annals of Mathematics
volume = 41
year = 1940
pages = 771–777
doi = 10.2307/1968857
*citation
last1 = Doignon
first1 = Jean-Paul
authorlink1 = Jean-Paul Doignon
last2 = Falmagne
first2 = Jean-Claude
authorlink2 = Jean-Claude Falmagne
title = Knowledge Spaces
year = 1999
publisher = Springer-Verlag
isbn = 3-540-64501-2
*cite book
author = Glasserman, Paul; Yao, David D.
title = Monotone Structure in Discrete Event Systems
year = 1994
series = Wiley Series in Probability and Statistics
publisher = Wiley Interscience
id = ISBN 978-0471580416

*cite journal
author = Gordon, Gary
title = A β invariant for greedoids and antimatroids
journal = Electronic Journal of Combinatorics
volume = 4
year = 1997
issue = 1
pages = Research Paper 13
id = MathSciNet | id = 1445628
url = http://www.combinatorics.org/Volume_4/Abstracts/v4i1r13.html

*cite book
author = Korte, Bernard; Lovász, László; Schrader, Rainer
year = 1991
title = Greedoids
publisher = Springer-Verlag
id = ISBN 3-540-18190-3
pages = 19–43
*cite conference
author = Parmar, Aarati
title = Some Mathematical Structures Underlying Efficient Planning
booktitle = AAAI Spring Symposium on Logical Formalization of Commonsense Reasoning
date = 2003
url = http://www-formal.stanford.edu/aarati/papers/SS603AParmar.pdf