In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumptions of finiteness. Geometric lattices and matroid lattices, respectively, form the lattices of flats of finite and infinite matroids, and every geometric or matroid lattice comes from a matroid in this way.
Contents
Definition
Recall that a lattice is a poset in which any two elements
(Following are several definitions for posets in general that are relevant to this article's topic. Since lattices are posets, all these definitions apply to lattices as well.)
In a poset an element
In a poset an element
In a poset the atoms are the elements that cover some minimal element of the poset.
A lattice is said to be atomistic if every element is the lub of some set of atoms.
A poset is graded when it can be given a rank function
When a graded poset has a bottom element, one may assume, without loss of generality, that its rank is zero. In this case, the atoms are the elements with rank one.
A graded lattice is semimodular if, for every
A matroid lattice is a lattice that is both atomistic and semimodular. A geometric lattice is a finite matroid lattice.
Some authors consider only finite matroid lattices, and use the terms "geometric lattice" and "matroid lattice" interchangeably for both.
Cryptomorphism
The geometric lattices are cryptomorphic to (finite, simple) matroids, and the matroid lattices are cryptomorphic to simple matroids without the assumption of finiteness.
Like geometric lattices, matroids are endowed with rank functions, but these functions map sets of elements to numbers rather than taking individual elements as arguments. The rank function of a matroid must be monotonic (adding an element to a set can never decrease its rank) and they must be submodular functions, meaning that they obey an identity similar to the one for semimodular lattices:
The maximal sets of a given rank are called flats. The intersection of two flats is again a flat, defining a greatest lower bound operation on pairs of flats; one can also define a least upper bound of a pair of flats to be the (unique) maximal superset of their union that has the same rank as their union. In this way, the flats of a matroid form a matroid lattice, or (if the matroid is finite) a geometric lattice.
Conversely, if
These two constructions, of a simple matroid from a lattice and of a lattice from a matroid, are inverse to each other: starting from a geometric lattice or a simple matroid, and performing both constructions one after the other, gives a lattice or matroid that is isomorphic to the original one.
Duality
There are two different natural notions of duality for a geometric lattice
Additional properties
Every interval of a geometric lattice (the subset of the lattice between given lower and upper bound elements) is itself geometric; taking an interval of a geometric lattice corresponds to forming a minor of the associated matroid. Geometric lattices are complemented, and because of the interval property they are also relatively complemented.
Every finite lattice is a sublattice of a geometric lattice.