Originators:Stefan Felsner and Tom Trotter (presented by Jeong Ok Choi - REGS 2008)
Definition: Given a poset P, define a graph GP whose vertices are the ordered pairs of incomparable elements of P, such that (x,y) is adjacent to (x',y') precisely when y≤x' and y'≤x.
Question 1: For t>2, does there exist a poset P such that dim(P)=t and χ(GP)=3?
Background: The condition for adjacency is equivalent to the nonexistence of a linear extension L of P having x<y and x'<y' in L. The dimension is the minimum size of a set of linear extensions such that x<y in P if and only if x<y in every linear extension in the set. Thus dim(P)≥χ(GP). Felsner and Trotter [FT] showed that dim(P)≤2 if and only if χ(GP)≤2. Felsner and Trotter wondered how in general to associate to a poset P a graph G such that dim(P)=χ(G). The question posed here is to show how far the poset GP is from doing the job.
The further motivation for seeking such a graph is that there is a richer hypergraph with the same vertex set as GP whose chromatic number does equal dim(P). An alternating cycle is a cyclic arrangement of ordered incomparable pairs (x1,y1),...,(xk,yk) such that yi≤xi+1 for all i. The pairs in an alternating cycle cannot appear in any linear extension, but any set of pairs not containing an alternating cycle can appear in a single linear extension. Hence dim(P) is the chromatic number of the hypergraph whose edges are the sets of incomparable pairs forming alternating cycles.
Comments:Let [n] denote the set {1,...,n}. The "standard" n-dimensional poset Sn is the containment poset on the singleton sets 1,...,n and their complements 1̅,...,n̅ in [n]. Here the pairs of the form (i̅,i) form a clique in GSn, so χ(GSn)=n=dim(Sn). Hence this family is not a good candidate for this problem.
We seek a sequence of posets with unbounded dimension for which there are few alternating cycles of size 2. A family that may be worth considering (suggested by Jeong Ok Choi) consists of the "universal" interval orders of each height. The elements of In are the real intervals having both endpoints in [n]. The order relation is that [a,b]<[c,d] if b<c. Bogart, Rabinovitch, and Trotter [BRT] showed that dim(In) increases without bound.
Question 2: What is the value of χ(GIn) as a function of n?
References:
[BRT] Bogart, K. P.; Rabinovich, Issie; Trotter, W. T., Jr.; A bound on the
dimension of interval orders. J. Combinatorial Theory Ser. A 21 (1976), no.
3, 319--328.
[FT] S. Felsner and W. Trotter; Dimension, Graph and Hypergraph Coloring,
Order, 17 (2000), pp. 167-177.