기초과학연구원 이산수학그룹
On June 16, 2021, Alan Lew from the Technion gave an online talk at the Virtual Discrete Math Colloquium on extending a classical theorem of Roberts on an upper bound of the boxicity of graphs to the d-boxicity of simplicial complexes. The title of his talk was “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 d-representable complexes. These are simplicial complexes that carry the information on the intersection patterns of a family of convex sets in $mathbb 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 $frac{1}{d+1}binom{n}{d}$.
Examples based on Steiner systems show that our result is sharp. The proofs combine geometric and topological ideas.