Dimension preserving contractions and a finite list of 3-irreducible posets (Q766141): Difference between revisions

The dimension of an ordered set \((P,\leq )\) is the smallest size for a set of linear orders (also called a realizer) whose intersection is the order \(\leq \). Of particular interest in dimension theory are \(t\)-irreducible ordered sets, which have dimension \(t\) and all their ordered subsets have dimension at most \(t-1\). The list of \(3\)-irreducible ordered sets consists of 10 ordered sets and 7 infinite classes of ordered sets; see [\textit{W. T. Trotter jun.} and \textit{J. I. Moore jun.}, Discrete Math. 16(1976), 361--381 (1977; Zbl 0356.06007); \textit{D. Kelly}, Can. J. Math. 29, 367--383 (1977; Zbl 0357.06004)]. For \(t\geq 4\), the classes of \(t\)-irreducible ordered sets have withstood characterization attempts. This paper introduces the \(1\)-contraction and \(2\)-contraction operations for ordered sets. The contractions apply to substructures in the \(7\) infinite classes of \(3\)-irreducible ordered sets. Moreover, under the right conditions on the realizers of the ordered set, which the author includes in the definition of each contraction, the contractions preserve the dimension. It is also shown that, without the hard to verify conditions on the realizers, \(1\)-contraction does not preserve the dimension. Operations of this kind present a chance to reduce classes of \(t\)-irreducible ordered sets by, in addition to every subset having dimension smaller than \(t\), demanding that the ordered set does not allow a dimension-preserving contraction. The author proceeds to prove that, in each of the \(7\) infinite classes of \(3\)-irreducible ordered sets, the smallest ordered set in the class is the only one that does not allow a dimension-preserving contraction. The operations themselves are the first of their kind, as in ordered sets it is uncommon to replace a structure with a different structure: typically the requirement that orders must be transitive makes such replacements cumbersome and prevents the replacement from preserving structural properties. The conditions on the realizers that are needed to assure that the contraction preserves the dimension also bear witness to the subtleties that come with replacing structures in ordered sets. To this day, there is no widely used analogue of the operation of a graph minor in order theory. Interestingly, the \(1\)-contraction the author introduces is essentially the composition of what this reviewer would consider an ``edge contraction for ordered sets'' and the deletion of a vertex. It would be nice if these operations were to grow into a useful analogue of graph minors in order theory.