Back to Search
Start Over
Representability and Boxicity of Simplicial Complexes.
- Source :
-
Discrete & Computational Geometry . Sep2022, Vol. 68 Issue 2, p592-607. 16p. - Publication Year :
- 2022
-
Abstract
- 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 R d . We define the d-boxicity of X as the minimal k such that X can be written as the intersection of kd-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 σ ⊊ τ . We prove that the d-boxicity of a simplicial complex on n vertices without missing faces of dimension larger than d is at most ⌊ n d / (d + 1) ⌋ . 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 n d / (d + 1) . One of the main ingredients in the proof is the following bound on the representability of a complex: let V 1 , ... , V k be subsets of V such that V i ∉ X for all 1 ≤ i ≤ k , and for any missing face τ of X there is some 1 ≤ i ≤ k satisfying | τ \ V i | ≤ 1 . Then, X can be written as an intersection X = ⋂ i = 1 k X i , where, for all 1 ≤ i ≤ k , X i is a (| V i | - 1) -representable complex. In particular, X is (∑ i = 1 k (| V i | - 1)) -representable. [ABSTRACT FROM AUTHOR]
- Subjects :
- *CONVEX sets
*STEINER systems
Subjects
Details
- Language :
- English
- ISSN :
- 01795376
- Volume :
- 68
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Discrete & Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 158671983
- Full Text :
- https://doi.org/10.1007/s00454-021-00332-1