Dimension, graph and hypergraph coloring (Q1590179)

A linear extension \(L\) of a poset \(P\) reverses an incomparable pair \((x,y)\) of \(P\) if \(x>y\) in \(L\). A set \(S\) of incomparable pairs forms a strict alternating cycle of \(P\) if no linear extension of \(P\) reverses all pairs in \(S\) but for all \(T \subset S\) there is a linear extension of \(P\) which reverses all pairs in \(T\). For a poset \(P = (X,\leq)\) let \(H_P = (V,E)\) be the hypergraph of incomparable pairs defined by \(V = \{(x,y) : x,y \in X\) and \(x \|y\}\) and \(E = \{S : S \subseteq V\) is a strict alternating cycle of \(P\}\). The graph of incomparable pairs is \(G_P = (V,E')\) with \(E' = \{S : S \in E\) and \(|S|=2\}\). Then dim\((P) = \chi(H_P) \geq \chi(G_P)\). The paper provides a new proof of the following theorem by Cogis: dim\((P)=2\) if and only if \(\chi(G_P)=2\) for every poset \(P\) that is not a total order. For all \(t \geq 2\) a poset \(P_t\) of dimension dim\((P_t) \geq (3/2)^{t-1}\) is constructed such that the chromatic number fulfills \(\chi(G_{P_t}) \leq 3t-4\).