| Dimension, graph and hypergraph coloring (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. There is a natural way to associate with a poset P a hypergraph HP, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of HP. The ordinary graph GP of incomparable pairs determined by the edges in HP of size 2 can have chromatic number substantially less than HP. We give a new proof of the fact that the dimension of P is 2 if and only if GP is bipartite. We also show that for each t 2, there exists a poset P for which the chromatic number of the graph of incomparable pairs is t, but the dimension of P is at least (3=2) t\Gamma1. However, it is not known whether there is a function f: R! R so that if P is a poset and the graph of incomparable pairs has chromatic number at most t, then the dimension of P is at most f(t). | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||