Antimatroid | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

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, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts. The axioms defining antimatroids as set systems are very similar to those of matroids, 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 greedoids and of semimodular lattices, and as a generalization of partial orders and of distributive lattices. Antimatroids are equivalent, by complementation, to convex geometries, a combinatorial abstraction of convex sets in geometry. Antimatroids have been applied to model precedence constraints in scheduling problems, potential event sequences in simulations, task planning in artificial intelligence, and the states of knowledge of human learners. An antimatroid can be defined as a finite family of finite sets, called feasible sets, with the following two properties: The union of any two feasible sets is also feasible. That is, is closed under unions. If is a nonempty feasible set, then contains an element for which (the set formed by removing from ) is also feasible. That is, is an accessible set system. Antimatroids also have an equivalent definition as a formal language, that is, as a set of strings defined from a finite alphabet of symbols. A string that belongs to this set is called a word of the language. A language defining an antimatroid must satisfy the following properties: Every symbol of the alphabet occurs in at least one word of .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (10)

Related lectures (4)

Family of sets

In set theory and related branches of mathematics, a collection of subsets of a given set is called a family of subsets of , or a family of sets over More generally, a collection of any sets whatsoever is called a family of sets, set family, or a set system. A family of sets may be defined as a function from a set , known as the index set, to , in which case the sets of the family are indexed by members 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 can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders.

Antimatroid

Explores VC dimension, gradient descent, convex sets, and Lipschitz functions in convex optimization.

Explores convex polyhedra, linear programs, and their optimization importance.

Covers set theory operations, functions, and their properties such as injective, surjective, and bijective functions.