Diagrams, orientations, and varieties (Q911621)

Given a poset P, a diagram for P consists of vertices in the plane in one-one correspondence with those of P and such that if \(a<b\) in P, then a is placed below b in the plane, and there is an edge (ab) connecting them if b covers a as well. A covering graph of P is the graph whose vertices are the elements of P and whose edges are the pairs (ab) representing the covering relation. Diagrams determine posets, covering graphs do not. As a class of graphs covering graphs are interesting for obvious reasons. Similarly diagrams when classified induce classifications of posets, which are taken to be finite in this paper. The classification tool used in this very interesting paper is the poset adaptation of the notion of ``variety'', which here means ``closed under - retract'' and ``closed under Cartesian product'', where ``-'' means graph, diagram or poset as the case may be. Other ``varieties'' studied widely are those closed under operations such as \(+\) (disjoint sum) and \(\oplus\) (ordinal on linear sum) which include the series-parallel posets for example. Retract-product varieties for diagrams (or posets) are denoted by RP(K), where RP(K) is the smallest retract-product variety containing a class of ordered sets. This operation \(K\subseteq RP(K)\) is a classical closure operator. Thus, e.g., finite distributive lattices are the retract-product variety generated by the two element chain. If a diagram variety V is closed with respect to orientations, i.e., O(V)\(\subseteq V\), then it corresponds naturally to a variety of covering graphs. Given a class K of posets, since OR(K)\(\subseteq RO(K)\), then \(K^ v=ROP(K)\) is the (retract-product) orientation variety associated with K. Given a class K of posets, I(K) denotes the class of all ordered sets constructed from K by inversion, which is any finite sequence of operation constructions named `pushdown', or `pullup'. The authors show that \(K^ v=RIPO(K)\) and that the class of posets whose covering graphs are median graphs is the variety \(RIPO(K_ 2)=RIP(2)=RIP(C_ 2)\), where \(2=C_ 2\) is the two element chain. Alternating cover-cycles play a central role in a number of important ``exclusion''-theorems. The authors demonstrate that for finite posets P, \(O(P)=I(P)\) iff no reorientation contains an alternating cover-cycle. Furthermore all such finite posets together form an orientation variety. The authors also show that the classes of posets with a reorientation of minimum height h or of maximum height h are reorientation varieties.