# Is it possible to compute the face lattice of a polytope from its vertex-facet incidences?

HI there,

I wonder if within sage it is possible to compute the face lattice of a polytope from its vertex-facet incidences. There is a known algorithm by Kaibel and Pfetsch (see https://arxiv.org/pdf/math/0106043.pdf), and we wonder if it has already been implemented in Sage.

Thanks, and regards, Guillermo

edit retag close merge delete

Sort by ยป oldest newest most voted

From Sage version 8.9+, on, the class CombinatorialPolyhedron can do just that.

Here is an example with your suggested Egyptian pyramid:

sage: ep = CombinatorialPolyhedron([[4,3,2,1],[4,3,0],[4,2,0],[3,1,0],[2,1,0]]); ep
A 3-dimensional combinatorial polyhedron with 5 facets
sage: fl_ep = ep.face_lattice(); fl_ep
Finite lattice containing 20 elements
sage: ep.f_vector()
(1, 5, 8, 5, 1)
sage: ep_poly = polytopes.regular_polygon(4).pyramid()
sage: fl_ep_poly = ep_poly.face_lattice()
sage: fl_ep_poly.is_isomorphic(fl_ep)
True


So far, there are a few things you can call on ep like edge graph, and ridges, and a fast iterator on the faces.

more

By searching the documentation or the source files of Sage, you can get an answer.

Searching doc:

sage: search_doc('Kaibel')
html/en/reference/geometry/sage/geometry/polyhedron/base.html:1166:<tr><td class="label"><a class="fn-backref" href="#id1">[KP2002]</a></td><td>Volker Kaibel and Marc E. Pfetsch, &#8220;Computing the Face


Searching source:

sage: search_src('Kaibel')
geometry/polyhedron/base.py:3195:            Volker Kaibel and Marc E. Pfetsch, "Computing the Face


Online documentation (append the result of "search_doc" to "http://doc.sagemath.org/").

http://doc.sagemath.org/html/en/reference/geometry/sage/geometry/polyhedron/base.html#sage.geometry.polyhedron.base.Polyhedron_base.face_lattice

more

Hi slelievre,

Thank you for your reply. Sage computes the face lattice of a polytope using Kaibel and Pfetsch's algorithm. So a polytope must be given. However, for you to construct a polytope in Sage you need either vertex coordinates or hyperplane equations; that is, you need a geometric realisation of the polytope.

Vertex-facet incidences is a combinatorial object which doesn't know about a geometric realisation. For instance, the following gives the vertex-facet incidences of the Egyptian pyramid [[4,3,2,1],[4,3,0],[4,2,0],[3,1,0],[2,1,0]], where the [4, 3, 2, 1] are the vertices of one facet.

( 2016-11-16 08:58:04 +0200 )edit