Geometric lattice

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.

Definition

A lattice is a poset in which any two elements $x$ and $y$ have both a supremum, denoted by $x\vee y$ , and an infimum, denoted by $x\wedge y$ .

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

For a minimal element $x$ , there is no element $y$ such that $y<x$ .
An element $x$ covers another element $y$ (written as $x:>y$ or $y<:x$ ) if $x>y$ and there is no element $z$ distinct from both $x$ and $y$ so that $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 $r(x)$ mapping its elements to integers, such that $r(x)>r(y)$ whenever $x>y$ , and in particular $r(x)=r(y)+1$ whenever $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 $x$ and $y$ , its rank function obeys the identity[1]

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]

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

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 inequality similar to the one for semimodular lattices:

r(X)+r(Y)\geq r(X\cap Y)+r(X\cup Y).\,

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 $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]

Duality

There are two different natural notions of duality for a geometric lattice $L$ : the dual matroid, which has as its basis sets the complements of the bases of the matroid corresponding to $L$ , and the dual lattice, the lattice that has the same elements as $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 $L$ (or of the matroid defined from it) to be a minimal geometric lattice into which the dual lattice of $L$ is order-embedded. Some matroids do not have adjoints; an example is the Vámos matroid.[6]

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

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

gollark: These people are INSANE.

gollark: > A TLV variable name is a random pronounceable three-letter string, sometimes with some vague relationship to its meaning, but usually not. Usually CVC (consonant-vowel-consonant) is a good choice.WHY WOULD YOU DO THIS

gollark: Isn't a u16 a "word" anyway?

gollark: What was wrong with `u64` or something?

gollark: ```c typedef uint64_t c3_d; // double-word typedef int64_t c3_ds; // signed double-word typedef uint32_t c3_w; // word typedef int32_t c3_ws; // signed word typedef uint16_t c3_s; // short typedef int16_t c3_ss; // signed short typedef uint8_t c3_y; // byte typedef int8_t c3_ys; // signed byte typedef uint8_t c3_b; // bit```Wow, this is HIGHLY readable.

References

Birkhoff (1995), Theorem 15, p. 40. More precisely, Birkhoff's definition reads "We shall call P (upper) semimodular when it satisfies: If a≠b both cover c, then there exists a d∈P which covers both a and b" (p.39). Theorem 15 states: "A graded lattice of finite length is semimodular if and only if r(x)+r(y)≥r(x∧y)+r(x∨y)".
Maeda, F.; Maeda, S. (1970), Theory of Symmetric Lattices, Die Grundlehren der mathematischen Wissenschaften, Band 173, New York: Springer-Verlag, MR 0282889.
Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 388, ISBN 9780486474397.
Welsh (2010), p. 51.
Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, 25 (3rd ed.), American Mathematical Society, p. 80, ISBN 9780821810255.
Cheung, Alan L. C. (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin, 17 (3): 363–365, correction, ibid. 17 (1974), no. 4, 623, doi:10.4153/CMB-1974-066-5, MR 0373976.
Welsh (2010), pp. 55, 65–67.
Welsh (2010), p. 58; Welsh credits this result to Robert P. Dilworth, who proved it in 1941–1942, but does not give a specific citation for its original proof.

External links

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Birkhoff (1995), Theorem 15, p. 40. More precisely, Birkhoff's definition reads "We shall call P (upper) semimodular when it satisfies: If a≠b both cover c, then there exists a d∈P which covers both a and b" (p.39). Theorem 15 states: "A graded lattice of finite length is semimodular if and only if r(x)+r(y)≥r(x∧y)+r(x∨y)".

[2] Maeda, F.; Maeda, S. (1970), Theory of Symmetric Lattices, Die Grundlehren der mathematischen Wissenschaften, Band 173, New York: Springer-Verlag, MR 0282889.

[3] Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 388, ISBN 9780486474397.

[w10-51-4] Welsh (2010), p. 51.

[5] Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, 25 (3rd ed.), American Mathematical Society, p. 80, ISBN 9780821810255.

[6] Cheung, Alan L. C. (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin, 17 (3): 363–365, correction, ibid. 17 (1974), no. 4, 623, doi:10.4153/CMB-1974-066-5, MR 0373976.

[7] Welsh (2010), pp. 55, 65–67.

[8] Welsh (2010), p. 58; Welsh credits this result to Robert P. Dilworth, who proved it in 1941–1942, but does not give a specific citation for its original proof.