This page contains historical information about a workshop held in the past.

Date and Location

17 November 2016, RMIT University (Melbourne, Australia)

About the Workshop

An informal gathering of those interested in the geometry of polytopes.

The meeting was sponsored by RMITOpt (RMIT Optimisation group).

Participants

Serdar Boztas (RMIT University)
Reinier Diaz Millan (Federal Institute of Goias and UniSA)
Andrew Eberhard (RMIT University)
David Ellison (RMIT University)
David Kirszenblat (University of Melbourne) On Hirsch conjecture
Fei Lu (RMIT University)
Michael Nyblom (RMIT University)
William Pettersson (RMIT University)
Guillermo Pineda-Villavicencio (Federation University Australia) The excess degree of a polytope and some of its applications
Vera Roshchina (RMIT University)
Hyam Rubinstein (University of Melbourne) On Hirsch conjecture
Tian Sang (RMIT University)
James Saunderson (Monash University) Lifts of polytopes and non-negative rank
Sergei Schreider (RMIT University)
David Yost (Federation University Australia) Lower bound theorems and decomposability for polytopes
Sanming Zhou (University of Melbourne)

Location

Room 8.9.66 (Access grid room), RMIT City Campus.

Organisers (RMIT)

Andrew Eberhard
Sharon Kirby
Fabricio Oliveira
Vera Roshchina
Tian Sang

Program

Time	Duration	Talk
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
12:00–14:00		Lunch
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

Selected Talks

Speaker: David Yost (Federation University Australia)

Title: Lower bound theorems and decomposability for polytopes

Abstract:

For a $d$ -dimensional polytope with $v$ vertices, $d+1 \le v \le 2d$ , we calculate precisely the minimum possible number of $m$ -dimensional faces, when $m = 1$ or $m \ge 0.62d$ . This confirms a conjecture of Grünbaum, for these values of $m$ . We also characterise the minimising polytopes. For $v = 2d+1$ , the same problem is solved for $m = 1, d - 1$ or $d - 2$ .

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 ( $\le2d+1$ ) vertices, and the decomposable polytopes with few ( $\le(d+3)(d-1)$ ) edges.

There is significant interaction between these two topics. Stronger conclusions are available when $d=3$ .

Speaker: Guillermo Pineda-Villavicencio

Title: The excess degree of a polytope and some of its applications

Abstract: We define the excess degree $e(P)$ of a $d$ -polytope $P$ as $2f_1-df_0$ , where $f_0$ and $f_1$ denote the number of vertices and edges of the polytope, respectively.

We first prove that the excess degree of a $d$ -polytope does not take every natural number: the smallest values are $0$ and $d-2$ , with the value $d-1$ only occurring when $d=3$ or $5$ . On the other hand, if $d$ is even, the excess degree takes every even natural number from $d\sqrt{d}$ onwards; while, if $d$ is odd, the excess degree takes every natural number from $d\sqrt{2d}$ onwards.

Our study of the excess degree is then applied in four different settings. We show that polytopes with small excess (i.e., $e(P)=d-2$ , $d-1$ ) 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 $d$ -polytopes with excess $d$ which are decomposable and $d$ -polytopes which are not. Secondly, we characterise the decomposable $d$ -polytopes with at most $2d+1$ vertices. Here we are only concerned with combinatorial decomposability: a polytope $P$ is (combinatorially) decomposable if whenever $Q$ is combinatorially equivalent to $P$ (equivalent face lattices), $Q$ is decomposable.Thirdly, we characterise all pairs $(f_0,f_1)$ for which there exists a 5-polytope with $f_0$ vertices and $f_1$ edges. And, fourthly, we characterise the $d$ -polytopes with at most $2d+2$ 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 $P$ , is a description $P=\pi(Q)$ where $\pi$ is a linear map and $Q$ is another polytope in a higher dimensional space. If $Q$ has many fewer facets than $P$ , such a description is useful from the point of view of optimisation. The smallest number of facets of an LP-lift of $P$ is called its extension complexity. This talk describes the (elementary) connection, made by Yannakakis in 1991, between the extension complexity of $P$ and the non-negative rank of a certain matrix associated with the polytope $P$ . 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 $Q$ is replaced with a larger class of convex sets called spectrahedra, also of interest in optimisation.