$d$-representability of simplicial complexes of fixed dimension

Martin Tancer

Abstract


Let K be a simplicial complex with vertex set V = v1,…,vn. The complex K is d-representable if there is a collection {C1,…,Cn} of convex sets in Rd such that a subcollection {Ci1,…,Cij} has a nonempty intersection if and only if {vi1,…,vij} is a face of K.

In 1967 Wegner proved that every simplicial complex of dimension d is (2d+1)-representable. He also conjectured that his bound is the best possible, i.e., that there are d-dimensional simplicial complexes which are not 2d-representable. However, he was not able to prove his conjecture.

We prove that his suggestion was indeed right. Thus we add another piece to the puzzle of intersection patterns of convex sets in Euclidean space.


Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v2i1a9

ISSN: 1920-180X