Skip to main content
3 of 3
added 70 characters in body
Igor Makhlin
  • 3.5k
  • 1
  • 18
  • 25

I think I might've stumbled upon the answer I was looking for. It's the correspondence between interval greedoids and semimodular lattices. An interval greedoid is a pair $(E,\mathcal F)$ where $\mathcal F\subset 2^E$ is the family of feasible sets satisfying the accessibility property of antimatroids, the exchange property of matroids (these two properties define a greedoid) together with an additional interval property. In particular, it is easily seen that the feasible sets of an antimatroid (e.g. the order ideals of a poset) and the independent sets of a matroid both form interval greedoids. Below I mostly follow Section 2 in this paper by Saliola and Thomas although similar ideas can be traced back at least to a 1984 paper by Henry Crapo.

First, define the flats of a finite greedoid $(E,\mathcal F)$ as the equivalence classes of a relation on $\mathcal F$ given by $X\sim Y$ iff $$\{Z\subset E\backslash X|X\cup Z\in\mathcal F\}=\{Z\subset E\backslash Y|Y\cup Z\in\mathcal F\}$$ (a.k.a. $X$ and $Y$ have the same set of continuations). Fortunately, for our needs it is sufficient to consider unions of equivalence classes: I'll call subsets of $E$ having the form $\bigcup_{Y\sim X} Y$ for some $X\in\mathcal F$ the quasi-flats of $(E,\mathcal F)$ (for lack of a better term). For instance, the quasi-flats of a matroid are its flats and the quasi-flats of an antimatroid are its feasible sets. It turns out that ordering these quasi-flats by inclusion provides an upper semimodular lattice (see Propositions 2.7 and 2.9).

Conversely, given a finite upper semimodular lattice $L$, one may, as before, consider its set of join-irreducibles $P$ and let $\mathcal Q\subset 2^P$ denote the family of decompositions of all elements of $L$. An interval greedoid on $P$ with set of quasi-flats $\mathcal Q$ can be recovered as follows. Its family $\mathcal F\subset 2^P$ of feasible sets consists of all $\{p_1,\dots,p_k\}$ for which there exists a saturated chain $\varnothing=Q_0\subset\dots\subset Q_k$ in $\mathcal Q$ such that $p_i\in Q_i\backslash Q_{i-1}$ (it's an interval greedoid by Proposition 2.2, the quasi-flats statement needs to be checked separately).

The above procedures generalize both Birkhoff's theorem (a special case of the correspondence between antimatroids and join-distributive lattices) and the correspondence between matroids and geometric lattices. Now, apart from the fact that I'm absolutely new to all of this and hope that the above does not contain any blatant mistakes, there's one more thing I'm still wrapping my mind around. Evidently, going from a lattice to a greedoid and then back produces the original lattice, however, going from a greedoid to a lattice and back may not (I don't think an interval greedoid is even uniquely defined by its quasi-flats). This means that finite upper semimodular lattices are in bijection not with all finite interval greedoids but with a certain subclass which I'm yet to put my finger on. Maybe I'll update this answer if I come up with a concise statement. Also, I have no idea about the categorical meaning here, I don't think categories of greedoids have really been defined or studied.

Igor Makhlin
  • 3.5k
  • 1
  • 18
  • 25