The maximum diameter of pure simplicial complexes and pseudo-manifolds

Abstract

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

References in corpus (1)

• Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Cited by in corpus (1)

• On the diameter of dual graphs of Stanley-Reisner rings with Serre $(S_2)$ property and Hirsch type bounds on abstractions of polytopes