Representability and boxicity of simplicial complexes

Seminar
Speaker
Alan Lew (Technion)
Date
20/12/2020 - 15:30 - 14:00Add to Calendar 2020-12-20 14:00:00 2020-12-20 15:30:33 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.  Zoom אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Zoom
Abstract

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. 

תאריך עדכון אחרון : 20/12/2020