Thumbnail Image
🆕 Date Issued:
2020-09-23
🗄 Date Available:2021-03-05
Article

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

Randomized construction of complexes with large diameter

Criado, Francisco; Newman, Andrew

FG Diskrete Mathematik / Geometrie

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
Creative Commons Attribution 4.0 (CC BY)Creative Commons Attribution 4.0 (CC BY)
Full item page