This tutorial is probably also available as a Jupyter notebook in the `demo`

folder in the polymake source and on github.

Different versions of this tutorial: latest release, release 3.5, release 3.4, release 3.3, nightly master

# Tutorial on Polytopes

A *polytope* is the convex hull of finitely many points in some Euclidean space. Equivalently, a polytope is the bounded intersection of finitely many affine halfspaces. `polymake`

can deal with polytopes in both representations and provides numerous tools for analysis.

This tutorial first shows basic ways of defining a polytope from scratch. For larger input (e.g. from a file generated by some other program) have a look at our HowTo on loading data in `polymake`

.

The second part demonstrates some of the tool `polymake`

provides for handling polytopes by examining a small example. For a complete list of properties of polytopes and functions that `polymake`

provides, see the polytope documentation.

## Constructing a polytope from scratch

### V-Description

To define a polytope as the convex hull of finitely many points, you can pass a matrix of coordinates to the constructor. Since `polymake`

uses homogeneous coordinates, you need to set the additional coordinate x_{0} to 1.

> $p = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]]);

The `POINTS`

can be any set of coordinates, they are not required to be irredundant nor vertices of their convex hull. To compute the actual vertices of our polytope, we do this:

> print $p->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1

You can also add a lineality space via the input property `INPUT_LINEALITY`

.

> $p2 = new Polytope(POINTS=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1],[1,0,0]],INPUT_LINEALITY=>[[0,1,0]]);

To take a look at what that thing looks like, you can use the `VISUAL`

method:

> $p2->VISUAL;

See here for details on visualizing polytopes.

If you are sure that all the points really are *extreme points* (vertices) and your description of the lineality space is complete, you can define the polytope via the properties `VERTICES`

and `LINEALITY_SPACE`

instead of `POINTS`

and `INPUT_LINEALITY`

. This way, you can avoid unnecessary redundancy checks.

The input properties `POINTS`

/ `INPUT_LINEALITY`

may not be mixed with the properties `VERTICES`

/ `LINEALITY_SPACE`

. Furthermore, the `LINEALITY_SPACE`

**must be specified** as soon as the property `VERTICES`

is used:

> $p3 = new Polytope<Rational>(VERTICES=>[[1,-1,-1],[1,1,-1],[1,-1,1],[1,1,1]], LINEALITY_SPACE=>[]);

### H-Description

It is also possible to define a polytope as an intersection of finitely many halfspaces, i.e., a matrix of inequalities.

An inequality a_{0} + a_{1} x_{1} + … + a_{d} x_{d} >= 0 is encoded as a row vector (a_{0},a_{1},…,a_{d}), see also Coordinates for Polyhedra. Here is an example:

> $p4 = new Polytope(INEQUALITIES=>[[1,1,0],[1,0,1],[1,-1,0],[1,0,-1],[17,1,1]]);

To display the inequalities in a nice way, use the `print_constraints`

method.

> print_constraints($p4->INEQUALITIES); 0: x1 >= -1 1: x2 >= -1 2: -x1 >= -1 3: -x2 >= -1 4: x1 + x2 >= -17

The last inequality means 17+x_{1}+x_{2} ≥</html> 0, hence it does not represent a facet of the polytope. If you want to take a look at the acutal facets, do this:

> print $p4->FACETS; 1 1 0 1 0 1 1 -1 0 1 0 -1

If your polytope lies in an affine subspace then you can specify its equations via the input property `EQUATIONS`

.

> $p5 = new Polytope(INEQUALITIES=>[[1,1,0,0],[1,0,1,0],[1,-1,0,0],[1,0,-1,0]],EQUATIONS=>[[0,0,0,1],[0,0,0,2]]);

Again, if you are sure that all your inequalities are facets, you can use the properties `FACETS`

and `AFFINE_HULL`

instead. Note that this pair of properties is dual to the pair `VERTICES`

/ `LINEALITY_SPACE`

described above.

## Convex Hulls

Of course, `polymake`

can convert the V-description of a polytope to its H-description and vice versa. Depending on the individual configuration polymake chooses one of the several convex hull computing algorithms that have a `polymake`

interface. Available algorithms are double description (cdd of ppl), reverse search (lrs), and beneath beyond (internal). It is also possible to specify explicitly which method to use by using the `prefer`

command:

> prefer "lrs"; # use lrs until revoked by another 'prefer' or 'reset_preference "lrs"' > $p = new Polytope(POINTS=>[[1,1],[1,0]]); > print $p->FACETS; polymake: used package lrs Implementation of the reverse search algorithm of Avis and Fukuda. Copyright by David Avis. http://cgm.cs.mcgill.ca/~avis/lrs.html 1 -1 0 1

## A Neighborly Cubical Polytope

`polymake`

provides a variety of standard polytope constructions and transformations. This example construction introduces some of them. Check out the documentation for a comprehensive list.

The goal is to construct a 4-dimensional cubical polytope which has the same graph as the 5-dimensional cube. It is an example of a *neighborly cubical* polytope as constructed in

- Joswig & Ziegler: Neighborly cubical polytopes. Discrete Comput. Geom. 24 (2000), no. 2-3, 325–344, DOI 10.1007/s004540010039

This is the entire construction in a few lines of `polymake`

code:

> $c1 = cube(2); > $c2 = cube(2,2); > $p1x2 = product($c1,$c2); > $p2x1 = product($c2,$c1); > $nc = conv($p1x2,$p2x1);

Let us examine more closely what this is about. First we constructed a square `$c1`

via calling the function `cube`

. The only parameter `2`

is the dimension of the cube to be constructed. It is not obvious how the coordinates are chosen; so let us check.

> print $c1->VERTICES; 1 -1 -1 1 1 -1 1 -1 1 1 1 1

The four vertices are listed line by line in homogeneous coordinates, where the homogenizing coordinate is the leading one. As shown the vertices correspond to the four choices of `+/-1`

in two positions. So the area of this square equals four, which is verified as follows:

> print $c1->VOLUME; 4

Here the volume is the Euclidean volume of the ambient space. Hence the volume of a polytope which is not full-dimensional is always zero.

The second polytope `$c2`

constructed is also a square. However, the optional second parameter says that `+/-2`

-coordinates are to be used rather than `+/-1`

as in the default case. The optional parameter is also allowed to be `0`

. In this case a cube with `0/1`

-coordinates is returned. You can access the documentation of functions by typing their name in the `polymake`

shell and then hitting F1.

The third command constructs the polytope `$p1x2`

as the cartesian product of the two squares. Clearly, this is a four-dimensional polytope which is combinatorially (even affinely) equivalent to a cube, but not congruent. This is easy to verify:

> print isomorphic($p1x2,cube(4)); 1 > print congruent($p1x2,cube(4)); 0

Both return values are boolean, represented by the numbers `1`

and `0`

, respectively. This questions are decided via a reduction to a graph isomorphism problem which in turn is solved via `polymake`

's interface to `nauty`

.

The polytope `$p2x1`

does not differ that much from the previous. In fact, the construction is twice the same, except for the ordering of the factors in the call of the function `product`

. Let us compare the first vertices of the two products. One can see how the coordinates are induced by the ordering of the factors.

> print $p1x2->VERTICES->[0]; 1 -1 -1 -2 -2 > print $p2x1->VERTICES->[0]; 1 -2 -2 -1 -1

In fact, one of these two products is obtained from the other by exchanging coordinate directions. Thats is to say, they are congruent but distinct as subsets of Euclidean 4-space. This is why taking their joint convex hull yields something interesting. Let us explore what kind of polytope we got.

> print $nc->SIMPLE, " ", $nc->SIMPLICIAL; 0 0

This says the polytope is neither simple nor simplicial. A good idea then is to look at the f-vector. Beware, however, this usually requires to build the entire face lattice of the polytope, which is extremely costly. Therefore this is computationally infeasible for most high-dimensional polytopes.

> print $nc->F_VECTOR; 32 80 72 24

This is a first hint that our initial claim is indeed valid. The polytope constructed has 32 vertices and 80 = 32*5/2 edges, as many as the 5-dimensional cube:

> print cube(5)->F_VECTOR; 32 80 80 40 10

What is left is to check whether the vertex-edge graphs of the two polytopes actually are the same, and if all proper faces are combinatorially equivalent to cubes.

> print isomorphic($nc->GRAPH->ADJACENCY,cube(5)->GRAPH->ADJACENCY); 1 > print $nc->CUBICAL; 1

See the tutorial on graphs for more on that subject.