Skip to main content
added 955 characters in body
Source Link
Igor Makhlin
  • 3.5k
  • 1
  • 18
  • 25

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!

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.)

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!

Became Hot Network Question
added 9 characters in body
Source Link
Igor Makhlin
  • 3.5k
  • 1
  • 18
  • 25

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$ contains someincludes a subset containing exactly one of $A$ such that$p$ and $p\in A\not\ni q$$q$. But I'm not sure where to go from here.)

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$ contains some $A$ such that $p\in A\not\ni q$. But I'm not sure where to go from here.)

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.)

Source Link
Igor Makhlin
  • 3.5k
  • 1
  • 18
  • 25

Birkhoff's representation theorem vs matroid-geometric lattice correspondence

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$ contains some $A$ such that $p\in A\not\ni q$. But I'm not sure where to go from here.)