The dimension of cycle-free orders (Q1803661)

Given a poset \(X\), if the comparability graph of \(X\) contains a cycle without chords to connect vertices at distance at least two along the cycle, then it is of even length and it generates a bipartite subset of a particular sort. Cycle-free comparability graphs are thus of an intuitively simpler kind, a fact borne out by the observation that many of the combinatorial problems for posets, such as the determination of the jump number problem for example, are polynomial in this class rather than NP-complete. Thus, it was known that cycle-free posets actually exist. Given that four-dimensional posets are rather complicated in most cases, if they are not members of some standard families, it is not surprising that the example that the authors have been able to come up with is a quite formidable one whose construction as well as the argument on evaluation of the dimension require considerable meditation aided by nifty diagrams. After providing the example, the authors also point the way to several other similar problems in the area of dimension theory for classes of posets of interest to them, i.e., interval orders and circle orders.