Date:
Mon, 09/11/2020
HUJI Combinatorics Seminar
Speaker: Alan Lew (Technion)
When: Monday Nov 9th, 2020 11AM
Zoom link: https://huji.zoom.us/j/89975674747?pwd=MXFCSmlhMEJVTXoyTm5pUU1zb1B4Zz09
Title: Representability and boxicity of simplicial complexes
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 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.
Speaker: Alan Lew (Technion)
When: Monday Nov 9th, 2020 11AM
Zoom link: https://huji.zoom.us/j/89975674747?pwd=MXFCSmlhMEJVTXoyTm5pUU1zb1B4Zz09
Title: Representability and boxicity of simplicial complexes
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 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.