The graph of critical pairs of a crown (Q2279688)

To any poset \(P\) one can associate a hypergraph \(\mathcal{H}\) of critical pairs such that the chromatic number of \(\mathcal{H}\) is equal to the dimension of \(P\). The chromatic number of the subgraph \(G\), on the same vertex set, comprising the hyperedges with two elements thus gives a lower bound on the dimension of \(P\). While the gap between this lower bound and the truth can be arbitrarily large, quite often the lower bound is the true dimension. The main aim of the article under review was originally to show this equivalence for a class of posets called crowns (the crown \(S_{n}^{k}\) is a height 2 poset with minimal elements \(A=\{a_{1},a_{2},\ldots a_{n+k}\}\) and maximal elements \(B=\{b_{1},b_{2},\ldots b_{n+k}\}\) and with \(a_{i}\) and \(b_{j}\) comparable precisely when \(j\not\in \{i,i+1,\ldots i+k\}\) where of course all indices are read modulo \(n+k\). Crowns have long been known to be important in the study of dimension, for example the crowns with \(k=0\) are the posets on \(2n\) vertices with the largest possible dinension \(n\) (for \(n\geq 4\)). More generally, \(S_{n}^{k}\) has dimension \(2(n+k)/(k+2)\). In the end, the authors prove the desired result by showing that the independence number of the graph \(G_{n}^{k}\) associated with \(S_{n}^{k}\) is \((k+1)(k+2)/2\), as part of a more detailed study of independent sets in \(G_{n}^{k}\). This gives the result, using the standard fact that the chromatic number is the least number of vertices divided by the independence number, as one can check that \(G_{n}^{k}\) has \((n+k)(k+1)\) vertices. The proofs involve, inter alia, splitting the class of independent sets into so-aclled reversible ones and non-reversible ones, with the analysis for non-reversible ones requiring distinction of two cases \(n\leq k\) and \(k < n \leq 2k\).