Poset boxicity of graphs (Q1103652)

A t-box representation of a graph encodes each vertex as a box in t-space determined by the (integer) coordinates of its lower and upper corner, such that vertices are adjacent if and only if the corresponding boxes intersect. The boxicity of a graph G is the minimum t for which this can be done; equivalently, it is the minimum t such that G can be expressed as the intersection graph of intervals in the t-dimensional poset that is the product of t chains. Scheinerman defined the poset boxicity of a graph G to be the minimum t such that G is the intersection graph of intervals in some t-dimensional poset. In this paper, a special class of posets is used to show that the poset boxicity of a graph on n points is at most O(log log n). Furthermore, Ramsey's theorem is used to show the existence of graphs with arbitrarily large poset boxicity.