Randomized construction of complexes with large diameter

Abstract

We consider the question of the largest possible combinatorial diameter among pure dimensional and strongly connected (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^varTheta (d) of the upper bound. We also make a similar improvement in the case of pseudomanifolds.