On the dimension of posets with cover graphs of treewidth 2 (Q2407679): Difference between revisions

The main result of this paper is a proof of the fact that any poset whose cover graph has treewidth at most \(2\) has order dimension (or dimension) at most \(1276\). Here, the (order) dimension of a poset is the smallest number of linear extensions that realize the poset and the cover graph of a poset is a simple graph on the elements of the poset that represents the Hasse diagram of the poset. \textit{W. T. Trotter jun.} and \textit{J. I. Moore jun.} proved in [J. Comb. Theory, Ser. B 22, 54--67 (1977; Zbl 0307.06003)] that a poset whose cover graph has treewidth at most one (so it is a forest) has dimension at most 3. On the other hand, a well-known construction by \textit{D. Kelly} [Discrete Math. 35, 135--156 (1981; Zbl 0468.06001)] shows there are posets of arbitrarily large dimensions whose cover graphs are planar and of treewidth \(3\). In fact, the examples of Kelly [loc.cit.] are of planar cover graphs that contain the ``standard example \(S_n\)'' of dimension \(n\), as a subposet. Recent work shows that a poset has dimension at most \(4\) if its cover graph is outerplanar [\textit{S. Felsner} et al., Graphs Comb. 31, No. 4, 927--939 (2015; Zbl 1328.06004)] and it has dimension at most \(17\) if its cover graph has pathwidth at most \(2\) [\textit{C. Biró} et al., Order 33, No. 2, 195--212 (2016; Zbl 1364.06002)]. These last two recent results strongly suggested to the authors that posets whose cover graphs have treewidth at most \(2\) have bounded dimension, which is proved in this present paper, namely that the dimension is at most \(1276\). The proof is long and technical, and according to the authors themselves, the optimal upper bound of the dimension is conjectured to be significantly lower than \(1276\).