Randomized construction of complexes with large diameter

Abstract

We consider the question of the largest possible combinatorial diameter among $(d-1)$-dimensional simplicial complexes on $n$ vertices, denoted $H_s(n,d)$. Using a probabilistic construction we give a new lower bound on $H_s(n,d)$ that is within an $O(d^2)$ factor of the upper bound. This improves on the previously best-known lower bound which was within a factor of $e^{\Theta (d)}$ of the upper bound. We also make a similar improvement in the case of pseudomanifolds.

14 pages