This page contains historical information about a workshop held in the past.
17 November 2016, RMIT University (Melbourne, Australia)
An informal gathering of those interested in the geometry of polytopes.
The meeting was sponsored by RMITOpt (RMIT Optimisation group).
Room 8.9.66 (Access grid room), RMIT City Campus.
|9:30–10:20||Coffee and snacks for those who arrive early|
|10:20–10:45||20 + 5 mins||Hyam Rubinstein, on Hirsch conjecture|
|10:45–11:10||20 + 5 mins||David Kirszenblat, on Hirsch conjecture (continued)|
|11:10–11:55||40 + 5 mins||David Yost, Lower bound theorems and decomposability for polytopes|
|14:00–14:50||45 + 5 mins||Guillermo Pineda-Villavicencio, The excess degree of a polytope and some of its applications|
|14:50–15:25||30 + 5 mins||James Saunderson, Lifts of polytopes and non-negative rank|
|15:30–17:00||Open problem session: David Ellison, Guillermo Pineda-Villavicencio, Vera Roshchina, Hyam Rubinstein|
Speaker: David Yost (Federation University Australia)
Title: Lower bound theorems and decomposability for polytopes
For a -dimensional polytope with vertices, , we calculate precisely the minimum possible number of -dimensional faces, when or . This confirms a conjecture of Grünbaum, for these values of . We also characterise the minimising polytopes. For , the same problem is solved for or .
A polytope (or more general convex set) is called decomposable if it can be expressed as the (Minkowski) sum of two dis-similar convex bodies. We classify large families of polytopes, as decomposable or not, by studying graph theoretic properties of their skeletons. In particular, we characterise completely the decomposable polytopes with few () vertices, and the decomposable polytopes with few () edges.
There is significant interaction between these two topics. Stronger conclusions are available when .
Speaker: Guillermo Pineda-Villavicencio
Title: The excess degree of a polytope and some of its applications
Abstract: We define the excess degree of a -polytope as , where and denote the number of vertices and edges of the polytope, respectively.
We first prove that the excess degree of a -polytope does not take every natural number: the smallest values are and , with the value only occurring when or . On the other hand, if is even, the excess degree takes every even natural number from onwards; while, if is odd, the excess degree takes every natural number from onwards.
Our study of the excess degree is then applied in four different settings. We show that polytopes with small excess (i.e., ,) behave in a similar manner to simple polytopes in terms of (Minkowski) decomposability: each such polytope is either decomposable or a pyramid, and their duals are always indecomposable. This is best possible since there are -polytopes with excess which are decomposable and -polytopes which are not. Secondly, we characterise the decomposable -polytopes with at most vertices. Here we are only concerned with combinatorial decomposability: a polytope is (combinatorially) decomposable if whenever is combinatorially equivalent to (equivalent face lattices), is decomposable.Thirdly, we characterise all pairs for which there exists a 5-polytope with vertices and edges. And, fourthly, we characterise the -polytopes with at most vertices and the minimum number of edges, answering in this way a 1969 conjecture of Grunbaum.
Speaker: James Saunderson, Monash University
Title: Lifts of polytopes and non-negative rank
Abstract: A LP-lift (or extended formulation) of a polytope , is a description where is a linear map and is another polytope in a higher dimensional space. If has many fewer facets than , such a description is useful from the point of view of optimisation. The smallest number of facets of an LP-lift of is called its extension complexity. This talk describes the (elementary) connection, made by Yannakakis in 1991, between the extension complexity of and the non-negative rank of a certain matrix associated with the polytope . This connection yields (some) methods to prove lower bounds on the extension complexity of polytope, a topic of recent interest among theoretical computer scientists. The aim of the talk is to describe these ideas, give some examples and questions, and if time permits, mention generalizations where is replaced with a larger class of convex sets called spectrahedra, also of interest in optimisation.