Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Randomized construction of complexes with large diameter
Author(s): Criado, Francisco
Newman, Andrew
Type: Article
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.
Subject(s): diameter
Hirsch conjecture
probabilistic method
simplicial complex
Issue Date: 23-Sep-2020
Date Available: 5-Mar-2021
Is Part Of: 10.14279/depositonce-11781
Language Code: en
DDC Class: 510 Mathematik
Sponsor/Funder: TU Berlin, Open-Access-Mittel – 2020
DFG, 385256563, GRK 2434: Facetten der Komplexität
Journal Title: Discrete and Computational Geometry
Publisher: SpringerNature
Publisher DOI: 10.1007/s00454-020-00248-2
EISSN: 1432-0444
ISSN: 0179-5376
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik » FG Diskrete Mathematik / Geometrie
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:

Item Export Bar

This item is licensed under a Creative Commons License Creative Commons