Workshop "Polytope Diameter and Related Topics"

As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize Workshop "Polytope Diameter and Related Topics" via Zoom on September 2 (based on European Timezone), 2022.

A basic idea is to share fundamental concepts and recent trends of polytope diameter and related topics. The question on polytope diameter is closely related to the performance of a combinatorial algorithm such as the simplex method for linear programming. It is a big open problem whether there exists a combinatorial polynomial-time algorithm for linear programming while known polynomial-time algorithms such as the ellipsoid method and the interior-point methods are not considered combinatorial. Several algorithmic challenges in linear programming and integer programming rely on properties on "diameter". A celebrated conjecture by Hirsch states that the diameter of a convex polytope is bounded from above by the number of facets minus the dimension. The conjecture was disproved by Santos, but a question still remains that the diameter can be bounded by a polynomial of the number of facets and the dimension. Furthermore, several questions on combinatorial upper bounds for reconfiguration problems are related to polytope diameter. For example, the diameter of an associahedron is equal to the maximum flip distance between two triangulations of a convex polygon. A breakthrough result by Sleator, Tarjan and Thurston gave a lower bound for that diameter with hyperbolic geometry, which has been well-known in theoretical computer science since it is also related to the rotation distance between rooted trees.

This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on this active research area.

The program will be exclusively composed of invited talks. Each talk is planned to span one hour, including discussion.

List of Confirmed Invited Speakers

• Jean Cardinal (Université Libre de Bruxelles, Belgium)
• Daniel Dadush (CWI, the Netherlands)
• Jesús De Loera (University of California, Davis, CA, USA)
• Hariharan Narayanan (Tata Institute of Fundamental Research, India)
• Vincent Pilaud (CNRS and École Polytechnique, France)
• Francisco Santos (University of Cantabria, Spain)

Program

• 8:20- 8:30 Organizer: Introduction to the workshop
• 8:30- 9:30 Hariharan Narayanan: A Spectral Approach to Polytope Diameter
• 9:45-10:45 Vincent Pilaud: Diameters of generalizations of the associahedron
• 11:00-12:00 Francisco Santos: Small topological counter-examples to the Hirsch Conjecture
• 12:00-14:00 Lunch and Free Discussion
• 14:00-15:00 Daniel Dadush: Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
• 15:15-16:15 Jean Cardinal: Flip graphs and polytopes
• 16:30-17:30 Jesús De Loera: On Polyhedra Parametrizing ALL pivot rules for the Simplex Method

Talk Titles and Abstracts

• Hariharan Narayanan (Tata Institute of Fundamental Research, India)
  Title: A Spectral Approach to Polytope Diameter
  Abstract: We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for integer polytopes in terms of the length of the description of the polytope (in bits) and the minimum angle between facets of its polar. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure 1 - o(1) and polynomial diameter. Both bounds rely on spectral gaps - of a certain Schrödinger operator in the first case, and a certain continuous time Markov chain in the second - which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables. This is a joint work with Rikhav Shah and Nikhil Srivastava.
  
• Vincent Pilaud (CNRS and École Polytechnique, France)
  Title: Diameters of generalizations of the associahedron
  Abstract: The diameter of the associahedron has been a longstanding fascinating problem with inspiring progress until its definitive combinatorial solution by L. Pournin. In this talk, I will discuss some results and problems about diameters and geodesic properties of generalizations of the associahedron.
  
• Francisco Santos (University of Cantabria, Spain)
  Title: Small topological counter-examples to the Hirsch Conjecture.
  Abstract:
  The Hirsch Conjecture claimed that the combinatorial diameter of a d-polytope with n facets should not exceed n-d. It was stated by Hirsch in 1957 and disproved by me in 2010 with a counter-example of dimension 43. In subsequent work with Matschke and Weibel we constructed a smaller counter-example, of dimension 20.
  Both constructions are based in the use of prismatoids, polytopes with all vertices contained in two disjoint facets, and in a d-step theorem for prismatoids, showing that any prismatoid of "width" larger than its dimension can be lifted to a non-Hirsch polytope.
  In this talk I will review this construction and report on recent work with F. Criado (Exp. Math. 2022) in which we look at topological prismatoids and use them to construct about 4000 non-Hirsch simplicial spheres of dimensions ranging from 8 to 20. Unfortunately, many of our spheres, including all those of dimensions less than 10, have been proved to be non-polytopal by Pfeifle and/or by Gouveia, Macchia and Wiebe.
• Daniel Dadush (CWI, the Netherlands)
  Title: Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
  Abstract: The combinatorial diameter $\mbox{diam}(P)$ of a polytope $P$ is the maximum shortest path distance between any pair of vertices. In this paper, we provide upper and lower bounds on the combinatorial diameter of a random "spherical" polytope, which is tight to within one factor of dimension when the number of inequalities is large compared to the dimension. More precisely, for an $n$-dimensional polytope $P$ defined by the intersection of $m$ i.i.d. half-spaces whose normals are chosen uniformly from the sphere, we show that $\mbox{diam}(P)$ is $\Omega(nm^{1/(n-1)})$ and $O(n^2m^{1/(n-1)}+n^5 4^n)$ with high probability when $m \geq \Omega(n)$.
  For the upper bound, we first prove that the number of vertices in any fixed two dimensional projection sharply concentrates around its expectation when $m$ is large, where we rely on the $\Theta(n^2m^{1/(n-1)})$ bound on the expectation due to Borgwardt [Math. Oper. Res., 1999]. To obtain the diameter upper bound, we stitch these “shadows paths” together over a suitable net using worst-case diameter bounds to connect vertices to the nearest shadow. For the lower bound, we first reduce to lower bounding the diameter of the dual polytope $P^o$, corresponding to a random convex hull, by showing the relation $\mbox{diam}(P) \geq (n-1)(\mbox{diam}(P^o)-2)$. We then prove that the shortest path between any “nearly” antipodal pair vertices of $P^o$ has length $\Omega(m^{1/n-1})$.
  
• Jean Cardinal (Université Libre de Bruxelles, Belgium)
  Title: Flip graphs and polytopes
  Abstract: We consider families of flip graphs that are skeletons of polytopes, ranging from the ubiquitous associahedra to hypergraphic polytopes, via graphical zonotopes. For each family, we describe recent results and open problems about diameters, flip distance computation, and Hamiltonian properties.
  
• Jesús De Loera (University of California, Davis, CA, USA)
  Title: On Polyhedra Parametrizing ALL pivot rules for the Simplex Method
  Abstract: The simplex method is one of the most famous and popular algorithms in optimization. The engine of any version of the simplex method is a pivot rule that selects the outgoing arc for a current vertex. Pivot rules come in many forms and types, but after 80 years we are still ignorant whether there is one that can make the simplex method run in polynomial time. This talk is about the polyhedral combinatorics of the simplex method. I will present two recent positive results: For 0/1 polytopes there are explicit pivot rules for which the number of non-degenerate pivots is polynomial and even linear (joint work with A. Black, S. Kafer, L. Sanita). I also present a parametric analysis for all pivot rules. We construct a polytope, the pivot rule polytope, that parametrizes all memoryless pivot rules of a given LP. Its construction is a generalization of the Fiber polytope construction of Billera Sturmfels. This is an attempt to get a complete picture of the structure “space of all pivot rules of an LP” (joint work with A. Black, N. Lütjeharms, and R. Sanyal).
  

Organizer

• Yoshio Okamoto (The University of Electro-Communications, Japan)