Ask Your Question
2

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

asked 2016-11-15 18:13:31 -0600

guillermo gravatar image

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 flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
3

answered 2019-08-27 15:04:46 -0600

jipilab gravatar image

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.

edit flag offensive delete link more
1

answered 2016-11-16 01:42:19 -0600

slelievre gravatar image

updated 2016-11-16 01:42:35 -0600

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

edit flag offensive delete link more

Comments

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.

guillermo gravatar imageguillermo ( 2016-11-16 01:58:04 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-11-15 18:13:31 -0600

Seen: 183 times

Last updated: Aug 27