Tree-width and dimension (Q2400108)

The important paper under review deals with the dimension of a finite partially ordered set (poset) \(P\) with \(n\) vertices. Here, the dimension of a poset is the smallest number of total orders compatible with the partial order whose intersection is the partial order: that is to say, the smallest \(r\) such that there are \(r\) total orders \(L_{1},L_{2},\ldots, L_{r}\) on the set for which we have \(x<y\) in \(P\) if and only if \(x<y\) in \(L_{i}\) for all \(1\leq i\leq r\). It has been known for some time that the height of a partial order (i.e., the length of the longest chain in it) does give much information per se about the dimension: for example, there are posets of height 2 -- the so-called \` standard examples\'\, with maximum possible dimension \(\lfloor n/2 \rfloor\). However, the insight of the paper under review is to bound the dimension above in terms of the height and the so-called tree width of the cover graph of the poset. The cover graph of a poset has vertex set the vertices of \(P\) and an edge between \(x\) and \(y\) if \(x<y\) and there is no \(z\in P\) such that \(x<z<y\), or if \(y<x\) and there is no \(z\in P\) with \(x<z<y\) (so that, for example, the cover graph of a chain is a path. The tree-width of a graph is a parameter of the graph: it is known that graphs with low tree-width are, in a very loose sense, \` tree-like\'\, and tend to have comparatively manageable properties. The exact result proved in the paper is that for any pair \((t,h)\) of positive integers there is \(d=d(t,h)\) such that any poset of height \(\leq h\) whose cover graph has tree-width \(\leq t\) has dimension \(\leq d\). In particular, it is shown that one can take \(d(t,h)\leq 6.2^{8t^{4h-2}}\) though this bound is likely to be far from optimal. This result generalises some older results about posets whose cover graph is planar. The proof uses the notion of the signature of an incomparable pair. The authors make several conjectures towards the end of the paper, a large number of which have now been resolved by various groups of authors.