Dimension and matchings in comparability and incomparability graphs. (Q5965146)

It is proved that, for every ordered set of dimension \(d\geq 3\), there is a matching of size \(d\) in the comparability graph as well as in the complement of the comparability graph. To prove these results, several inequalities are proved, and the inequalities are shown to be tight. It is also shown that, although there will be a matching of size \(d\) in the comparability graph, no such matching need exist in the cover graph. The paper gives a nice overview of salient results and conjectures in dimension theory that provides context for the new results. It is well written and easy to follow. Hence, with a little bit of work, it can serve as an introduction to dimension theory that showcases important results as well as fundamental techniques. The only stumbling block is a mistake in the last two paragraphs of the proof of Theorem 4.3. A conversation with the authors brought forth the following remedy that can replace the final two paragraphs of said proof: By Claim 2, \(\dim(P-\{u\})=d-1\), so \(u\) is not a minimal element. Hence, there is some \(i\) for which \(u>x_i\). By Claim 1, there is a maximal element \(w\not\in\{x_j,y_j:j=1,\ldots,m\}\) that is greater than \(y_i\). If \(u\not>y_i\), then \(w\neq u\). If \(u>y_i\), then, because \((u,v)\) is a critical pair, \(v>y_i\) and we can choose \(w:=v\neq u\). Thus, in the matching, the chain \(\{x_i<y_i\}\) can be replaced with the two chains \(\{x_i<u\}\) and \(\{y_i<w\}\), contradicting the fact that the matching was maximal.