f-vectors and decomposability of polytopes

Project Title:

f-vectors and decomposability of polytopes

Supervisors:

David Yost, Guillermo Pineda

Contact person and email address:

David Yost <d.yost@federation.edu.au>

A brief description of the project:

This project is concerned with the geometric properties of polytopes determined by their combinatorial structure, in particular their graphs, and methods to decompose them into simpler polytopes.

A polytope is the convex hull of a finite set in d-dimensional space. Familiar examples are the polygons in two dimensions and the Platonic solids in three dimensions. Important examples in higher dimensions are encountered in optimisation, where they occur as the feasible regions for linear programming problems. A typical algorithm will work by moving from one vertex to another, until an optimal solution is found. So it is of practical interest to bound the lengths of paths in a polytopes, and to estimate the total number of edges, for example in terms of the number of vertices or the number of maximal faces.

The Minkowski sum of two polytopes (or more general convex sets) Q and R is the set of points q+r with q in Q and r in R. A polytope P is called Minkowski decomposable if it can be expressed as the sum of two other polytopes which are not geometrically similar to it; similar means one can be obtained from the other by a positive scalar multiplication and a translation. Minkowski sums and decompositions arise in the definition of quasidifferentiable functions. Most nonsmooth optimisation algorithms today require the iterative calculation of descent directions. These calculations can be decomposed into simpler ones, if we know that our compact convex set can be decomposed. Minkowski sums and decompositions also have applications in other fields, such as collision detection and robotics, pattern recognition, and vision geometry.

Specific topics include the following.

1. Understanding the extent to which Minkowski decomposability of polytopes is determined by their face lattice. This topic is now well understood in three dimensions, but even the most basic questions remain open in higher dimensions. In particular, what restrictions does decomposability force on the f-vector of a polytope? Or even on the number of edges? Ambiguous examples, i.e. face lattices which do not give sufficient information to determine decomposability of the associated polytopes, have long been known in three dimensions, but examples remain to be found in higher dimensions.

2. Calculating the possible f-vectors of polytopes. This problem has only been solved in dimension three, and seems intractable in dimension four. Calculating the 2-dimensional projections of the f-vectors has been achieved in dimension four; extending this to dimensions five and above would be a significant achievement.

Research Environment: A prospective student will also have access to external supervisors (Julien Ugon (Deakin University) and Krzysztof Przeslawski (University of Zielona Gora, Poland) and corresponding opportunities to benefit from their research environment.

Research Output: The supervision team has already had demonstrable success in solving long-standing open question in the area, as demonstrated by the number of recent articles published in top-quartile journals. This research project will likewise have output in the form of publications in high profile journals.

* G. Pineda-Villavicencio, J. Ugon and D. Yost, Lower bound theorems for general polytopes, European Journal of Combinatorics, to appear, arXiv:1510.08258.

* G. Pineda-Villavicencio, J. Ugon and D. Yost, Polytopes close to being simple, Discrete & Computational Geometry, to appear, arXiv:1704.00854.

* E. Nevo, G. Pineda-Villavicencio, J. Ugon and D. Yost, Almost simplicial polytopes I. The lower and upper bound theorems, Canadian Journal of Mathematics, to appear, arXiv:1510.08258.

* G. Pineda-Villavicencio, J. Ugon and D. Yost, The excess degree of a polytope, SIAM Journal on Discrete Mathematics 32 (2018), 2011-2046.

* J. Doolittle, E. Nevo, G. Pineda-Villavicencio, J. Ugon and D. Yost, On the reconstruction of polytopes, Discrete & Computational Geometry, https://doi.org/10.1007/s00454-018-9997-9