## Alan Lew gave an online talk on extending the boxicity of graphs to simplicial complexes at the Virtual Discrete Math Colloquium

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“.

## Alan Lew, 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.

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209