Birkhoff's representation theorem vs matroid-geometric lattice correspondence

Question

This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says that for a finite distributive lattice $L$ with set of join-irreducible elements $P$ the subsets $\{p\in P|p\le a\}\subset P, a\in L$ form the set of order ideals of a partial order on $P$ (which uniquely defines the partial order). The latter says that if $L$ is, instead, a geometric lattice, then the same family of subsets is the set of flats for a matroid structure on $P$ (for a geometric lattice join-irreducible elements are precisely its atoms). The former provides a bijection between finite distributive lattices and finite posets, the latter provides a bijection between geometric lattices and finite simple matroids. Both bijections have functorial interpretations.

Broadly speaking, my question is: are there other interesting correspondences of this form and do these two phenomena have some interesting common generalization? More specifically, here is an example of what such a result may look like. We may consider an arbitrary (finite?) lattice $L$ with set of join-irreducible elements $P$ and define a family of subsets of $P$ in the same way. Does this family of subsets define some interesting algebraic structure on $P$? Perhaps, for some specific classes of lattices, maybe classes that include both geometric and distributive $L$? (Apparently, in full generality we can obtain any family which is closed under intersection, has least common supersets and for any $p,q\in P$ includes a subset containing exactly one of $p$ and $q$. But I'm not sure where to go from here.)

Update. Two further nice examples of such correspondences were given by Richard Stanley and Sam Hopkins.

• For finite join-distributive $L$ this family of subsets is the family of feasible sets of an antimatroid on $P$. This generalizes Birkhoff's representation theorem. See details here.
• In their 2019 paper Reading, Speyer and Thomas introduce the notion of a finite two-acyclic factorization system: a finite set equipped with a specific kind of binary relation. For a finite semidistributive lattice our family of subsets is the set of first components of maximal orthogonal pairs of such a binary relation on $P$ and the relation is recovered from this data.

I've accepted the first answer but I still very much hope to see other examples!

Answer 1

Antimatroids are a good example. We have the syllogism "Antimatroids are to matroids as join-distributive lattices are to geometric lattices." Two other examples are the characterizations of complemented modular lattices of finite length $n\geq 4$ and primary modular lattices of finite length $n\geq 4$. (A modular lattice of finite length is primary if for every join-irreducible $t$, the interval $[\hat{0},t]$ is a chain, and dually, e.g., the lattice of subgroups of a finite abelian group.) Their characterizations are analogous to characterizing finite distributive lattices as a collection of sets closed under union and intersection. See for instance Theorems 5 and 6 of Alan Day, Geometric applications in modular lattices, in Universal Algebra and Lattice Theory (Puebla, 1982), Springer Lecture Notes in Mathematics 1004, pp. 111-141. I don't know a common generalization of distributive and geometric lattices with the type of structure asked for.

Answer 2

In their recent papert "The fundamental theorem of finite semidistributive lattices" (https://doi.org/10.1007/s00029-021-00656-z and https://arxiv.org/abs/1907.08050) Reading, Speyer, and Thomas provide an abstract characterization of finite semi-distributive lattices as "factorization systems", extending Birkhoff's fundamental theorem of finite distributive lattices. Here for each element $x\in L$ of the lattice you need to record more information than the set $\{j\colon j \leq x, \textrm{$j$ is join-irreducible}\}$; you essentially also need to record the dual information of $\{m\colon m \geq x, \textrm{$m$ is meet-irreducible}\}$. So this representation theorem does not exactly fit your paradigm, but it is still very similar.

Answer 3

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.

Answer 4

The notion of a matroid can be formulated in terms of geometric lattices, closure systems, and closure operators. Furthermore, the finite pre-ordered sets can be considered to be precisely the finite topological spaces. The duality between geometry lattices and the closure system/closure operator formulation of matroids along with the duality between finite posets and finite distributive lattices are both special cases of a duality between closure systems, closure operators, and maps into posets.

A closure system on a set $X$ is a collection $C\subseteq P(X)$ which is closed under arbitrary intersection (including the empty intersection which means that $X\in C$). A closure operator on a set $X$ is a function $C:P(X)\rightarrow P(X)$ such that $R\subseteq C(R)=C(C(R))$ for $R\subseteq X$ and where $R\subseteq S\Rightarrow C(R)\subseteq C(S).$

If $C$ is a closure system, then define $C^*:P(X)\rightarrow P(X)$ by letting $C^*(R)$ be the smallest set in $C$ with $R\subseteq C^*(R)$. Then $C^*$ is a closure operator. If $C$ is a closure operator, then define $C^*=\{R\subseteq X\mid R=C(R)\}=\{C(R)\mid R\subseteq X\}$. Then $C$ is a closure system. If $C$ is a closure operator, then $C=C^{**}$, and if $C$ is a closure system, then $C=C^{**}$.

If $C$ is a closure system on a set $C$, then define a mapping $I(C):X\rightarrow C$ by letting $\iota(C)(x)=C^*(\{x\})$ for $x\in X$.

Recall that a subset $A$ of a complete lattice $L$ is said to be join dense if $\{\bigvee R\mid R\subseteq A\}=L$.

If $L$ is a complete lattice, and $\iota:X\rightarrow L$ is a function. Then define $M(\iota)=\{\iota^{-1}[\downarrow l]\mid l\in L\}$. Then $M(\iota)$ is a closure system on the set $X$. Then $I(C)[X]$ is join-dense in $C$.

Theorem:

1. Suppose that $C$ is a closure system on a set $X$. Then $M(I(C))=C$.

2. Suppose that $L$ is a complete lattice, and $\iota:X\rightarrow L$ is a function, then define a mapping $\phi:L\rightarrow M(\iota)$ by letting $\phi(l)=\iota^{-1}[\downarrow l]$. Define a mapping $\psi:M(\iota)\rightarrow L$ by letting $\psi(R)=\bigvee\iota[R]$ whenever $R\in C$. Then

i. $\psi(R)\leq\ell$ if and only if $R\subseteq\phi(\ell)$.

ii. if $\iota[X]$ is join-dense in $L$, then $\psi,\phi$ are inverses.

Proof:

1. If $\ell\in C$, then $x\in I(C)^{-1}[\downarrow\ell]$ iff $I(C)(x)\in\downarrow \ell$ iff $C^*(\{x\})\subseteq\ell$ iff $x\in\ell$. Therefore, $I(C)^{-1}(\downarrow \ell)=\ell$. We conclude that $ M(I(C))=\{I(C)^{-1}[\downarrow\ell]\mid \ell\in C\}=C.$

i. $x\in\phi(\bigwedge_{i\in I}\ell_i)$ iff $\ell(x)\in\downarrow\bigwedge_{i\in I}\ell_i$ iff $\ell(x)\leq\bigwedge_{i\in I}\ell_i$ iff $\ell(x)\leq\ell_i$ for $i\in I$ iff $x\in\ell^{-1}[\downarrow \ell_i]=\phi(\ell_i)$ for $i\in I$ iff $x\in\bigwedge_{i\in I}\phi(\ell_i)$. Therefore, $\phi(\bigwedge_{i\in I}\ell_i)=\bigwedge_{i\in I}\phi(\ell_i)$, so $\phi$ preserves arbitrary meets.

ii. We have $\psi(\phi(\ell))=\psi(\ell^{-1}[\downarrow\ell])=\bigvee\iota[\iota^{-1}[\downarrow\ell]]=\bigvee\{\ell(x)\mid\ell(x)\leq\ell\}=\ell$. Therefore $\phi$ is injective. $\phi$ is also surjective by definition.

Q.E.D.

Posets and distributive lattices

We say that a closure system $C$ is a topological closure system if $C$ is closed under finite unions (including the empty union, so $\emptyset\in C$).

We observe that if $L$ is a complete lattice, and $\iota:X\rightarrow L$ is a function with $\iota[X]$ join dense in $L$, then it is not too hard to show that $M(\iota)$ is a topological closure system if and only if $\iota(x)$ is join-prime for each $x\in X$. However, the finite topological closure systems can be put into a one-to-one correspondence with the finite pre-ordered sets; to get a pre-ordered set from a closure system, just take the specialization ordering on that closure system, and the downwards closed sets in a pre-ordered set form a closure system.

Thus, we obtain a duality between the finite pre-ordered sets $(X,\leq)$ and the functions $\iota:X\rightarrow L$ where $X$ is a finite set, $\iota[X]$ is join-dense in $L$, and each element in $\iota[X]$ is join-prime. This duality restricts to a duality between the finite posets $(X,\leq)$ and the collection of all functions $\iota:X\rightarrow L$ where $L$ is a distributive lattice, and $\iota$ is a bijection between $X$ and the set of all join-irreducible elements in $L$.

Answer 5

I learned that there is at least one precise answer to this exact question (more precise than my previous answer). The bijection between finite posets and finite distributive lattices and the bijection between finite simple matroids and geometric lattices are both generalized by the bijection between finite Faigle geometries and finite upper semimodular lattices. The following definition is due to a recent paper by Czédli, the notion itself originates in a 1980 paper by Faigle.

Definition (Defintion 2.1 in Czédli). A Faigle geometry $(P,\le,\mathcal F)$ consists of a poset $(P,\le)$ and a collection $\mathcal F\subset 2^P$ which only contains order ideals of $(P,\le)$, is closed under intersections and also contains $\varnothing$, $P$ and the order ideals $\{p|p\le q\}$ and $\{p|p<q\}$ for all $q\in P$. Moreover, if $X\in\mathcal F$ and $q\notin X$ but $p\in X$ for all $p<q$, then the minimal $Y\in\mathcal F$ containing both $X$ and $q$ must cover $X$ in $(\mathcal F,\subseteq)$.

For instance, $\mathcal F$ may consist of all order ideals in $(P,\le)$ or the order $\le$ may be trivial and $\mathcal F$ consist of the flats of a simple matroid on $P$. If $P$ is finite, then $(\mathcal F,\subseteq)$ is an upper semimodular lattice. If $(L,\le)$ is a finite upper semimodular lattice, then the procedure in my question produces a Faigle geometry $(P,\le,\mathcal F)$ where $P$ is the subset of join-irreducibles and $\mathcal F=\{\{p\in P|p\le a\}\}_{a\in L}$. These two correspondences are inverse to each other and define a bijection between the two classes (Theorem 2.5 in Czédli).