×

Combinatorial representation and convex dimension of convex geometries. (English) Zbl 0659.06005

The authors develop a representation theory for convex geometries in terms of labelled posets. These results may be viewed as representation theorems for meet-distributive lattices and are in this sense generalizations of Birkhoff’s representation theorem for distributive lattices. The crucial results are:
1) Let f be an onto function from a finite poset P to a finite set X. Then the collection \(\Phi (P,f)=\{C\subseteq X:\) \(C=\bar f(U)\) for U a filter of \(P\}\) of subsets of X is a convex geometry on the ground set X.
2) If (X,L) is a convex geometry and h the induced labeling of the poset of meet-irreducibles M(L), then \(\Phi (M(L),h)=L.\)
Both results provide a complete characterization of the convex geometries on the ground set X. Moreover the authors turn to the natural question: what properties of a convex geometry are determined by its meet-irreducibles? They define a “convex dimension” of a convex geometry cdim(X,L) and show that it depends only on the poset M(L), namely, \(c\dim (X,L)=w(M(L))\) \((w=width)\). Dilworth’s chain decomposition theorem is an essential tool in the proof of this result.
Reviewer: M.Stern

MSC:

06C10 Semimodular lattices, geometric lattices
52A37 Other problems of combinatorial convexity
PDF BibTeX XML Cite
Full Text: DOI