Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-11546
For citation please use:
Main Title: Randomized construction of complexes with large diameter
Author(s): Criado, Francisco
Newman, Andrew
Type: Article
Language Code: en
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.
URI: https://depositonce.tu-berlin.de/handle/11303/12746
http://dx.doi.org/10.14279/depositonce-11546
Issue Date: 23-Sep-2020
Date Available: 5-Mar-2021
DDC Class: 510 Mathematik
Subject(s): diameter
Hirsch conjecture
probabilistic method
simplicial complex
pseudomanifolds
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2020
DFG, 385256563, GRK 2434: Facetten der Komplexität
License: https://creativecommons.org/licenses/by/4.0/
Journal Title: Discrete and Computational Geometry
Publisher: SpringerNature
Publisher Place: London [u.a.]
Publisher DOI: 10.1007/s00454-020-00248-2
EISSN: 1432-0444
ISSN: 0179-5376
Appears in Collections:FG Diskrete Mathematik / Geometrie » Publications

Files in This Item:

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons