Representability and boxicity of simplicial complexes

An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology, Roberts defined the boxicity of a graph G to be the minimal k such that G can be written as the intersection of k interval graphs.

A natural higher dimensional generalization of interval graphs is the class of d-representable complexes. These are simplicial complexes that carry the information on the intersection patterns of a family of convex sets in R^d. We define the d-boxicity of a simplicial complex X to be the minimal k such that X can be written as the intersection of k d-representable complexes.
 

A classical result of Roberts, later rediscovered by Witsenhausen, asserts that the boxicity of a graph with n vertices is at most n/2. Our main result is the following high dimensional extension of Roberts' theorem: Let X be a simplicial complex on n vertices with minimal non-faces of dimension at most d. Then, the d-boxicity of X is at most (n choose d)/(d+1).

Examples based on Steiner systems show that our result is sharp. The proofs combine geometric and topological ideas.