vertex facet graph for trivial polyhedra fails

[kliem]

The vertex facet graph of CombinatorialPolyhedron only works for polyhedra of dimension at least one. With #29188 this makes it fail with for Polyhedron_base as well.

We fix this to return

• the Digraph on 0 vertices for the empty polyhedron and
• the Digraph on 1 vertex for the 0-dimensional polyhedron (it was misbehaved even before Move vertex facet graph to combinatorial polyhedron #29188).

We also "fix" the definition of facets to correspond to inequalities.
The 0-dimensional polyhedron does not have facets in this case anymore.
(Before this ticket n_facets and facets would use different definitions of facets.)

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedra, vertex facet graph

Author: Jonathan Kliem

Branch: 25cfaa0

Reviewer: Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/29898

[kliem]

Branch: public/29898

[kliem]

Commit: 790dfbc

[kliem]

New commits:

790dfbc

fix trivial vertex facet graphs

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d7cca49

correct fix for 0-dimensional polyhedron

[sagetrac-git]

Changed commit from 790dfbc to d7cca49

[mkoeppe]

comment:3

Does a 0-dimensional polyhedron really have a facet??

[kliem]

comment:4

I would say so. This is the "definition" from Günter Zieglers book "Lectures on Polytopes":

Also the empty set is a face for
every polytope. Less trivially, one has as faces the vertices of the polytope,
which are single points, the edges, which are 1-dimensional line segments,
and the facets, i.e., the maximal proper faces, whose dimension is one less
than that of the polytope itself.

According to this the facets of the 0-dimensional polytope is the empty face. And I would say that this is reasonable. There is also an inequality defining that face: "(0,...,0)*x + 1 >= 0" (and the 0-vector might have lenght 0 according to ambient dimension).
This is how it is currently handled in most parts

sage: P = Polyhedron([[0]])
sage: P.incidence_matrix()
[1]
sage: P.facets()
(A -1-dimensional face of a Polyhedron in ZZ^1,)

But of course, I might have be influential to "bug fixes" to make it behave like this.

[mkoeppe]

comment:5

Hm... the old version of Ziegler's at https://arxiv.org/pdf/math/9909177.pdf says "The maximal non-trivial faces, of dimension dim(P) − 1, are the facets of P." -- which excludes the empty face as a possibility.

[mkoeppe]

comment:6

I find the version that allows the empty face pretty disturbing.

[kliem]

comment:7

Either definition is trouble:

• If you define facets by correspondence with irreducible inequalites than the empty face of the 0-dimensional polytope is not a facet. However it is certainly maximal.
• If you define the facets by maximality than you loose that correspondence.