Thumbnail Image
🆕 Date Issued:
2020-09-23
🗄 In DepositOnce:2021-03-05
Published Version

Please use this identifier to cite or link to this item:

Randomized construction of complexes with large diameter

Criado, Francisco; Newman, Andrew

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.
diameterHirsch conjectureprobabilistic methodsimplicial complexpseudomanifolds
Is Part Of
10.14279/depositonce-11781
Published in: Discrete and Computational Geometry, 10.1007/s00454-020-00248-2, SpringerNature
Creative Commons Attribution 4.0 (CC BY)Creative Commons Attribution 4.0 (CC BY)
Full item page