Geometric lattice

A lattice is a poset in which any two elements ${\displaystyle x}$ and ${\displaystyle y}$ have both a least upper bound, called the join or supremum, denoted by ${\displaystyle x\vee y}$, and a greatest lower bound, called the meet or infimum, denoted by ${\displaystyle x\wedge y}$.

The following definitions apply to posets in general, not just lattices, except where otherwise stated.

• For a minimal element ${\displaystyle x}$, there is no element ${\displaystyle y}$ such that ${\displaystyle y<x}$.
• An element ${\displaystyle x}$ covers another element ${\displaystyle y}$ (written as ${\displaystyle x:>y}$ or ${\displaystyle y<:x}$) if ${\displaystyle x>y}$ and there is no element ${\displaystyle z}$ distinct from both ${\displaystyle x}$ and ${\displaystyle y}$ so that ${\displaystyle x>z>y}$.
• A cover of a minimal element is called an atom.
• A lattice is atomistic if every element is the supremum of some set of atoms.
• A poset is graded when it can be given a rank function ${\displaystyle r(x)}$ mapping its elements to integers, such that ${\displaystyle r(x)>r(y)}$ whenever ${\displaystyle x>y}$, and also ${\displaystyle r(x)=r(y)+1}$ whenever ${\displaystyle x:>y}$.

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 ${\displaystyle x}$ and ${\displaystyle y}$, its rank function obeys the identity[1]

${\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).\,}$

• A matroid lattice is a lattice that is both atomistic and semimodular.[2][3] A geometric lattice is a finite matroid lattice.[4]

Many authors consider only finite matroid lattices, and use the terms "geometric lattice" and "matroid lattice" interchangeably for both.[5]

The geometric lattices are equivalent to (finite) simple matroids, and the matroid lattices are equivalent to simple matroids without the assumption of finiteness (under an appropriate definition of infinite matroids; there are several such definitions). The correspondence is that the elements of the matroid are the atoms of the lattice and an element x of the lattice corresponds to the flat of the matroid that consists of those elements of the matroid that are atoms ${\displaystyle a\leq x.}$

Like a geometric lattice, a matroid is endowed with a rank function, but that function maps a set of matroid elements to a number rather than taking a lattice element as its argument. The rank function of a matroid must be monotonic (adding an element to a set can never decrease its rank) and it must be submodular, meaning that it obeys an inequality similar to the one for semimodular ranked lattices:

${\displaystyle r(X)+r(Y)\geq r(X\cap Y)+r(X\cup Y)}$

for sets X and Y of matroid elements. 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.[4]

Conversely, if ${\displaystyle L}$ is a matroid lattice, one may define a rank function on sets of its atoms, by defining the rank of a set of atoms to be the lattice rank of the greatest lower bound of the set. This rank function is necessarily monotonic and submodular, so it defines a matroid. This matroid is necessarily simple, meaning that every two-element set has rank two.[4]

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.[4]

There are two different natural notions of duality for a geometric lattice ${\displaystyle L}$: the dual matroid, which has as its basis sets the complements of the bases of the matroid corresponding to ${\displaystyle L}$, and the dual lattice, the lattice that has the same elements as ${\displaystyle L}$ in the reverse order. They are not the same, and indeed the dual lattice is generally not itself a geometric lattice: the property of being atomistic is not preserved by order-reversal. Cheung (1974) defines the adjoint of a geometric lattice ${\displaystyle L}$ (or of the matroid defined from it) to be a minimal geometric lattice into which the dual lattice of ${\displaystyle L}$ is order-embedded. Some matroids do not have adjoints; an example is the Vámos matroid.[6]

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.[7]

Every finite lattice is a sublattice of a geometric lattice.[8]

• "Geometric lattice", PlanetMath
• OEIS sequence A281574 (Number of unlabeled geometric lattices with n elements)