2020/08/23 by Lew, Alan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2008.09997
Let X be a simplicial complex on vertex set V. We say that X is d-representable if it is isomorphic to the nerve of a family of convex sets in ℝd. We define the d-boxicity of X as the minimal k such that X can be written as the intersection of k d-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of X is a set τ⊂ V such that τ∉ X but σ∈ X for any σ\subsetneq τ. We prove that the d-boxicity of a simplicial complex on n vertices without missing faces of dimension larger than d is at most \lfloor(1)/(d+1)\binomnd\rfloor. The bound is sharp: the d-boxicity of a simplicial complex whose set of missing faces form a Steiner (d,d+1,n)-system is exactly (1)/(d+1)\binomnd.