Compact way to output combinatorial type of 3-polytope

General discussion on polymake goes here.
mws
Posts: 32
Joined: 16 Jan 2014, 22:57

Compact way to output combinatorial type of 3-polytope

Postby mws » 07 Jul 2015, 14:31

What's a compact way to print out the combinatorial type of convex 3-polytope in polymake?

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: Compact way to output combinatorial type of 3-polytope

Postby paffenholz » 07 Jul 2015, 22:43

I am not exactly sure what you are aiming at. The full combinatorial type (the face lattice) can be computed from the vertex-facet incidence matrix

Code: Select all

print $p->VERTICES_IN_FACETS;
which gives you a sparse representation of the matrix where row j lists the vertices contained in the facet j.
This is of course not a fully unique representation as you can still permute the labelling of vertices and facets.

You can check for combinatorial isomorphy with

Code: Select all

print combinatorially_isomorphic($p,$q);
where you get a 1 if the polytopes are combinatorially isomoprhic and an empty result if not.

Andreas

mws
Posts: 32
Joined: 16 Jan 2014, 22:57

Re: Compact way to output combinatorial type of 3-polytope

Postby mws » 08 Jul 2015, 11:20

Thanks for your reply.

Let me explain in more detail what I am looking for. In my research I generate a lot of polytopes. I am mainly interested in \( f \)-vectors. However, since many of my polytopes have the same \( f \)-vector it would be nice to also know their combinatorial types. Given that I have a lot of polytopes, I cannot simply print out Hasse diagrams or adjacency matrices (besides them being not exactly human readable) for reasons of space.

One solution to this would be to print out the graph of a polytope (after sorting out isomorphic ones) as a graph6 string. This is very compact but definitely not human readable. From the graph we can then recover the combinatorial type.

Another idea is to use an old representation by Steinitz & Rademacher. They introduced something called "Polyederschema" which essentially assigns to every facet the number of vertices contained in cyclic order. By paying attention to a few more details, one can even achieve a unique word for each combinatorial type. The advantage of this scheme is its compactness and that one gets a good idea of how the polytope looks like.

But maybe there are even better or more compact ways to print out the combinatorial type?

Moritz

paffenholz
Developer
Posts: 211
Joined: 24 Dec 2010, 13:47

Re: Compact way to output combinatorial type of 3-polytope

Postby paffenholz » 08 Jul 2015, 12:12

I overlooked the restriction to dimension 3 in you question.

Then indeed the graph would suffice, but there is no shorter representation in polymake than the adjacency matrix (which is given as sets of neighbors for each vertex, so this should be human readable) or a list of all edges.

As the vertex-facet incidence matrix is given in sparse form as a list of vertices per facet this should be close to the densest form you can encode the combinatorial type (up to permutations, which also applies to the graph structures above). In the 3D-case you can get this cyclically ordered with

Code: Select all

print $p->VIF_CYCLIC_NORMAL;
which prints the vertices of each facet in cyclic order. Again, unique up to relabelling.

Andreas


Return to “General Discussion”