Antimatroid

From Wikipedia, the free encyclopedia

Three views of an antimatroid: an inclusion ordering on its family of feasible sets, a formal language, and the corresponding path poset.
Three views of an antimatroid: an inclusion ordering on its family of feasible sets, a formal language, and the corresponding path poset.

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.[1] 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.[2]

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, ... (sequence A119770 in OEIS).

Contents

[edit] 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:

  • No string in L contains two copies of the same symbol. That is, in the terminology of Korte et al., L is normal.
  • 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.[3]

[edit] Examples

A shelling sequence of a planar point set. The line segments show edges of the convex hulls after some of the points have been removed.
A shelling sequence of a planar point set. The line segments show edges of the convex hulls after some of the points have been removed.
  • 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.[4]
  • 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.[5]


[edit] 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 = \{U\setminus S\mid S\in 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.[6]

[edit] 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:

A\vee B = \{ S\cup T \mid S\in A \wedge T\in 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.[7]

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.[8] However, in general these two dimensions may be very different: there exist antimatroids with order dimension three but with arbitrarily large convex dimension.

[edit] Notes

  1. ^ E.g., see Gordon (1997).
  2. ^ See e.g. Doignon & Falmagne (1999), who refer to structures equivalent to antimatroids as "well-graded knowledge spaces".
  3. ^ Korte et al., Theorem 1.4.
  4. ^ Korte et al., Corollary 6.2.
  5. ^ 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.
  6. ^ Korte et al., Theorem 1.1.
  7. ^ Korte et al., Theorem 6.9.
  8. ^ Korte et al., Corollary 6.10.

[edit] References

  • Doignon, Jean-Paul & Falmagne, Jean-Claude (1999), Knowledge Spaces, Springer-Verlag, ISBN 3-540-64501-2 
  • Glasserman, Paul; Yao, David D. (1994). Monotone Structure in Discrete Event Systems, Wiley Series in Probability and Statistics. Wiley Interscience. ISBN 978-0471580416.