2015/01/12 by Fred B. Holt, Holt, Fred B.
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Commutative Algebra and Its Applications #Graph Labeling and Dimension Problems #math.CO #math.MG #msc:52B11
paper · pdf · doi:10.48550/arxiv.1501.02517
23 pages, 2 figures. arXiv admin note: text overlap with arXiv:1311.0581
arxiv created 2015/03/01 · arxiv updated 2015/03/03
In 2010 Santos described the construction of a counterexample to the Hirsch conjecture, and in 2012 Santos and Weibel provided the coordinates for the 40 facets of a 20-dimensional counterexample. In this paper we explore technical details of the construction using Santos and Weibel's work as the motivating example. Santos presented the construction in the dual setting. Here we return to the primal setting, in which Santos' construction calls for repeated application of a perturbed wedge operation, a wedge over a facet followed by a perturbation of one or more other facets. We show that the starting point for the construction is a counterexample "P5" to the nonrevisiting conjecture in dimension 5. However, this polytope P5 is not a simple polytope; it contains two nonsimple vertices. As we repeatedly apply the perturbed wedge, the nonsimplicities grow in dimension while their excess is reduced. Finally in dimension 20, the resulting polytope is simple and its diameter exceeds the Hirsch bound by 1. These notes are a technical companion to the work of Santos and Weibel.