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. 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 lattices, and can be characterized in several different ways.
- The description originally considered by Dilworth (1940) concerns meet-irreducible elements of the lattice. For each element x of an antimatroid, there exists a unique maximal feasible set Sx that does not contain x (Sx is the union of all feasible sets not containing x). Sx 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 Sx. 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 Sx whose meet is T; this family consists of the sets Sx 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 lattices, 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 (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 under which any finite distributive lattice has a representation as a family of sets closed under unions and intersections.
Read more about this topic: Antimatroid