Article ID Journal Published Year Pages File Type
6423705 Electronic Notes in Discrete Mathematics 2016 5 Pages PDF
Abstract

We construct d-dimensional pure simplicial complexes and pseudo-manifolds (with-out boundary) with n vertices whose combinatorial diameter grows as cdnd1 for a constant cd depending only on d, which is the maximum possible growth. Moreover, the constant cd is optimal modulo a singly exponential factor in d. The pure simplicial complexes improve on a construction of the second author that achieved cdn2d/3. For pseudo-manifolds without boundary, as far as we know, no construction with diameter greater than n2 was previously known.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,