Antimatroids as algebras

An antimatroid is most commonly described as a union-closed accessible family of sets, and they are also commonly formalized as prefix-closed formal languages satisfying a certain exchange axiom. Media theory leads to alternative formalizations involving geometric graphs and finite automata, and my work on drawing antimatroids leads to a characterization in terms of arrangements of translated orthants. But it turns out that antimatroids also have a fairly natural algebraic characterization. That is, we view antimatroids in terms of the algebraic properties of their union operation rather than as systems of explicit sets and elements.

The model for this is an algebraic description of semilattices and finite distributive lattices (equivalently, finite lattices of sets). A monoid consists of an associative binary operation (such as multiplication or string concatenation or function composition) on a set of objects, together with an identity object for the operation (such as, respectively, \( 1 \) or the empty string or the identity function); here we write the monoid operation as multiplication. A semilattice is a monoid that is commutative (\( xy=yx \) for all \( x,y \)) and idempotent (\( x^2=x \) for all \( x \)). The divisibility relation on a semilattice (\( x\mid y \) if, for some \( z \), \( xz=y \)) forms a partial order, and the semilattice operation can be interpreted as a join or least upper bound operation for that partial order. By analogy with ring theory we can define an irreducible object in a semilattice to be an \( x \) such that if \( x=yz \) then \( x=y \) or \( x=z \), and we can define a prime object in a semilattice to be an \( x \) such that if \( x\mid yz \) then \( x\mid y \) or \( x\mid z \). It turns out that the finite semilattices in which every irreducible is prime are exactly the ones that can be represented as the join operation for a finite distributive lattice; the lattice is formed by the union and intersection operations on lower sets of the restriction of the divisibility order to the primes.

To define antimatroids in a similar way, it seems to work best to turn the notion of irreducibility upside down: define \( s \) as singular, with successor \( t \), if \( s\ne t \) and for every \( x \) either \( sx=s \) or \( t\mid sx \). Then any finite semilattice can be represented as the union operation on sets, where the set corresponding to an object \( x \) consists of the singular objects that are not multiples of \( x \).

These sets always satisfy the union closure properties of antimatroids. It remains to formulate algebraic rules forcing these sets to also satisfy the accessibility requirement; that is, each nonempty set in the antimatroid must have a predecessor with one fewer element. The simplest rule I've found so far for this is the following: let \( x\mid y \), \( xa\ne xb \), and \( xa\ne ya=yb\ne xb \). Then there must exist \( z \) with \( x\mid z\mid y \) and \( x\ne z\ne y \). That is, if join operation with \( y \) covers up the differences between \( a \) and \( b \) but the join with \( x \) doesn't, and the joins of \( a \) and \( b \) with \( y \) differ from the corresponding joins with \( x \), then there must be an object \( z \) sandwiched between \( x \) and \( y \). Any antimatroid satisfies this rule, and I can prove that the singular set representation for any finite semilattice satisfying this rule forms an antimatroid. But the proof is somewhat tedious, so I'll just stop here.

Comments: