Abstract: We construct d-dimensional pure simplicial complexes and pseudo-manifolds (without boundary) with n vertices whose combinatorial diameter grows as cdnd - 1 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 cdn2 d / 3. For pseudo-manifolds without boundary, as far as we know, no construction with diameter greater than n2 was previously known.

Autoría

Descargar referencia