Randomized Construction of Complexes with Large Diameter
- PDF / 308,927 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 223 Views
Randomized Construction of Complexes with Large Diameter Francisco Criado1 · Andrew Newman1 Received: 12 June 2019 / Revised: 25 June 2020 / Accepted: 25 August 2020 © The Author(s) 2020
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 Hs (n, d). Using a probabilistic construction we give a new lower bound on Hs (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Θ(d) of the upper bound. We also make a similar improvement in the case of pseudomanifolds. Keywords Simplicial complex · Diameter · Hirsch conjecture · Probabilistic method Mathematics Subject Classification 05C12 · 05C15 · 05D40 · 05E45
1 Introduction Given a pure simplicial complex C, one may define the dual graph G(C) as the graph whose vertices are the top-dimensional faces of C and whose edges are pairs of top-dimensional faces that intersect at a face of codimension 1. Using standard terminology we refer to top-dimensional faces of C as facets and codimension 1 faces as ridges. From the definition of G(C), one defines the combinatorial diameter of C as the graph diameter of G(C). Of course, in general this may be infinite as G(C) need
Editor in Charge: Kenneth Clarkson A. Newman gratefully acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Graduiertenkolleg “Facets of Complexity” (GRK 2434). Francisco Criado [email protected] Andrew Newman [email protected] 1
Chair of Discrete Mathematics/Geometry, Technische Universität Berlin, Straße des 17. Juni 136, 10623 Berlin, Germany
123
Discrete & Computational Geometry
not be connected. Thus, here we consider the case where C is strongly connected, that is exactly the case that G(C) is connected. The best known situation in which the combinatorial diameter is considered is in the case when C is a simplicial polytope. In this situation there is the now-disproved [9] Hirsch conjecture which stated that if C is a simplicial polytope of dimension d with n vertices, then the diameter of C is at most n−d. While this is now known to be false, the polynomial Hirsch conjecture remains open. The polynomial Hirsch conjecture asserts that the combintorial diameter of a simplicial d-polytope on n vertices is bounded by a polynomial in n and d. On the other hand, the question can also be considered for other classes of simplicial complexes as a purely combinatorial question. Following the notation of [3], we define Hs (n, d) to be the largest combinatorial diameter of any strongly connected, pure (d − 1)-dimensional simplicial complex on n vertices. Observe that d is not the dimension of the complex, rather d − 1. This is to respect the notation for polyhedra, in which d refers to the dimension of the ambient space. In general, one could think of the d as the number of vertices in a facet. In [3], Criado and Santos prove the
Data Loading...
