Drums of high width

Alex Davies, Prateek Gupta, Sébastien Racanière, Grzegorz Swirszcz, Adam Zsolt Wagner, Theophane Weber, Geordie Williamson · 2025

Read Drums of high width by Alex Davies, Prateek Gupta, Sébastien Racanière, Grzegorz Swirszcz, Adam Zsolt Wagner, Theophane Weber, Geordie Williamson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-09919.txt.

Introduction

Davies and co-authors build a family of five-dimensional prismatoids whose width grows with their vertex count. Width here grows in a straight line as vertices are added. The family gives fresh counterexamples to the Hirsch conjecture. In these examples, the excess width grows linearly in the number of vertices as well. The result also answers a question posed by Matschke, Santos, and Weibel.

Catalog record

CREATORAlex Davies, Prateek Gupta, Sébastien Racanière, Grzegorz Swirszcz, Adam Zsolt Wagner, Theophane Weber, Geordie Williamson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE162 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-09919

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Drums of high width Thanks: GW is supported by ARC grant DP230102982. Alex Davies, Prateek Gupta, Sébastien Racanière, Grzegorz Swirszcz, Adam Zsolt Wagner, Theophane Weber, Geordie Williamson Abstract . We provide a family of 5 5 -dimensional prismatoids whose width grows linearly in the number of vertices. This provides a new infinite family of counter-examples to the Hirsch conjecture whose excess width grows linearly in the number of vertices, and answers a question of Matschke, Santos and Weibel. 1. Introduction Let P be a convex polytope. The graph of P has nodes and edges corresponding to the vertices and edges of P . It is a fundamental unsolved problem to determine the diameter of this graph: how many steps does one need in order to walk between any two vertices, if one may only traverse edges. This problem has deep connections to the complexity of the simplex method in linear programming. Indeed, lower bounds on the diameter of a polytope give lower bounds on the complexity of the simplex method. Determining the complexity of linear programming is one of Smale’s 18 problems, and is still unsolved. 1 1 1 See [ San12 , §1] for some interesting history on the diameter of polytopes and its connection to the complexity of linear programming. In 1957, Hirsch conjectured that the diameter of any convex polytope is bounded by n-d , where n is the number of facets and d is the dimension. This conjecture provides a simple linear bound for the diameter of a polytope, and would show that the diameter cannot provide a useful lower-bound for the complexity of the simplex method In a breakthrough paper in 2011, Santos [ San12 ] provided a counter-example to the Hirsch conjecture. His counter-example is in dimension 43 and has 86 facets, and the Hirsch bound fails by 1. Santos’ counter-example re-opens the door to the possibility that the diameter of polytopes might lead to interesting lower-bounds for the complexity of the simplex method. Motivated by the “ d -step theorem” of Klee and Walkup [ KW67 ] , Santos introduced the fundamental concept of a drum . 2 2 2 Drum is our terminology, Santos called them prismatoids These are polytopes with two parallel facets containing all vertices. A remarkable theorem of Santos shows that interesting drums in small dimension (e.g. 5), may be used to construct interesting polytopes in high dimension (e.g. 43 in Santos’ famous example). Experience suggests that the difficulty of gaining human understanding of polytopes grows exponentially in the dimension. This is one reason the drum concept is so useful—it allows one to compress high-dimensional difficulty into comparatively low dimension. More generally, the work of Santos and subsequent work of Maschke, Santos and Weibel [ MSW15 ] suggest that the study of drums may provide insights into the difficult question of the diameter of general polytopes. Despite considerable interest in this problem, there remain very few examples of polytopes breaking the Hirsch bound. All known examples arise from interesting 5-dimensional drums. Such “non-Hirsch drums” appear to have remarkable structure, and are extremely rare. In [ San12 ] , Santos provides examples with enormous numbers of facets to show that the Hirsch conjecture can fail by any constant amount. More recently, Maschke, Santos and Weibel [ MSW15 ] constructed more examples, showing that the excess width of drums (see below) can grow like the square root of the number of facets. In this paper we provide a family of 5-dimensional drums whose excess width grows linearly in the number of facets, answering a question posed in [ MSW15 ] . Up to a constant factor, this is best possible. We are also able to uncover the mechanism leading to such examples. 1.1. Main theorem As is often the case in the study of polytopes, it is useful to dualize. To a convex polytope P we may also associate its facet-ridge graph which has nodes given by the facets (=codimension 1 faces) of P and edges corresponding to ridges (=codimension 2 faces) of P . The facet-ridge graph of P agrees with the (vertex-edge) graph of the dual polytope. In this language the Hirsch conjecture states that the diameter of the facet-ridge of a convex polytope is bounded by n-d where n is the number of vertices of P and d is the dimension. As discussed above, in this paper we consider drums . These are polytopes D that posess two fixed parallel facets D^{-} and D^{+} (the drum skins ) which together contain all vertices of D . (For example, the cube and octahedron are both drums, with respect to any pair of opposite faces.) The width of a drum is the distance between the two drum skins in the facet-ridge graph. (Of course, the width of a drum provides a lower bound on the diameter of its facet-ridge graph.) Santos explained how to start with a d -dimensional drum with n vertices of width \geq w and produce another drum with 2(n-d) vertices in dimension n-d of diameter \geq w+n-2d . Thus, the Hirsch conjecture implies that drums in dimension d have width at most d . Santos constructs his counter-example starting from a 5-dimensional drum with 48 vertices of width 6>5 . More generally, Maschke, Santos and Weibel [ MSW15 ] suggested that the study of the width of drums might provide insights on the diameter of general polytopes. Thus, one is led to consider the function f_{d}(n)=\max_{\text{$d$-dimensional drums $D$ with $n$-vertices}}\width(D)-d. We call this function the excess width . The (disproved) Hirsch conjecture would have implied that this function is identically zero. All interesting examples so far involve 5-dimensional drums. The best results so far are due [ MSW15 ] and show that f_{5} grows at least as fast as the square root of n . Here we produce a new family of 5-dimensional drums D_{k} parametrized by k=1,2,\dots . They have 16k+24 vertices. Our main theorem is: Theorem 1.1 . D_{k} has width \geq 5+k . Thus our results prove that f_{5} grows linearly in n . The question of whether this is possible was raised in [ MSW15 ] . Note also that we hit (up to constants) the bounds established by [ MSW15 ] for 5-dimensional drums 3 3 3 Indeed, for any fixed constant d , the function f_{d}(n) is at most linear in n . . To translate this result back to the world of the Hirsch conjecture, Santos’ Strong d -step theorem for spindles, which was mentioned above, implies the following: Corollary 1.2 . For any integer k\geq 1 , there exists a polytope P_{k} of dimension d=16k+19 with 2d facets, that has diameter at least d+k . That is, the Hirsch bound fails by k . In [ San12 , §6] , Santos introduces the Hirsch excess of a (non-Hirsch) polytope which is defined as \frac{\delta}{n-d}-1 where \delta is its diameter, n the number of facets, and d the dimension. It is a useful measure of “how much” a polytope violates the Hirsch conjecture. One computes easily that the Hirsch excess of the polytopes arising from our family of drums is \frac{k}{16k+19} Thus, as k\rightarrow\infty the Hirsch excess of our

Read the complete text