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.

[kliem]

comment:8

Either way, I set up the vertex-facet graph wrong. There shouldn't be an edge, as the vertex is not contained in the facet.

[mkoeppe]

comment:9

Well the empty face is maximal in the proper faces but not maximal in the nontrivial faces.

[kliem]

comment:10

In the new definition that is different:

We consider the polytope itself as a trivial
face; all other faces are called proper faces

And then comes the part that I already quoted.

But...

The facets not corresponding to inequalities is huge trouble. I myself made "mistakes" because of that. It seems much easier to define the facets as maximal non-trival faces with the empty face being trivial as well.

Than we have our irreducible inequality/facet correspondence. So I agree with you that this definition makes more sense.

But that would involve a few "fixes".

I'll also send a quick note to Günter Ziegler and see what he thinks, as he is still revising his new definition I believe.

[kliem]

comment:11

An inequality is irredundant if and only if it defines a facet of P
and no multiple of it is contained in the system.

This statement is exercise 2.15 (iii) and clearly doesn't fit to the definition. Then again we loose the vertex-facet correspondence for polarity.

Btw the polarity for 0-dimensional polyhedra is broken as well (but only for base ring ZZ):

sage: P = Polyhedron([[]])
sage: P
A 0-dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex
sage: P.polar()
The empty polyhedron in ZZ^0

[kliem]

comment:12

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

[mkoeppe]

comment:13

Replying to @kliem:

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

Yes, this is not good.

[kliem]

comment:14

Replying to @mkoeppe:

Replying to @kliem:

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

Yes, this is not good.

The reason for this is simple. n_facets is just an alias of n_inequalities.

Either way, we cannot have it consistent:

• The class of polyhedra without inequalities doesn't have any facets.
• Facets of polyhedra correspond to coatoms of their face lattice.
• vertices of polytopes correspond to facets of their polar/dual.
• (irredundant) Inequalities of polyhedra correspond to facets.

I personally think that we should define facets as the d-1-faces of d-polyhedra.

But I have no hard feelings either way. It just should be made clear that the 0-polytope cannot be made consistent in some ways.

[mkoeppe]

comment:15

Either way, definitely n_facets() must be the same as the cardinality of facets().

To me, the bijection between facets and irredundant inequalities is the most important. Let me add that even the status of the empty set as a face is not uniform across the literature. For example, in Schrijver, Theory of Linear and Integer Programming, faces are nonempty by definition (section 8.3), and the face lattice is obtained by considering the empty set as a special element in addition to the faces (section 8.6).

[jplab]

comment:16

Replying to @mkoeppe:

Either way, definitely n_facets() must be the same as the cardinality of facets().

To me, the bijection between facets and irredundant inequalities is the most important. Let me add that even the status of the empty set as a face is not uniform across the literature. For example, in Schrijver, Theory of Linear and Integer Programming, faces are nonempty by definition (section 8.3), and the face lattice is obtained by considering the empty set as a special element in addition to the faces (section 8.6).

+1

Looking at the subsets of the polytope obtained through supporting hyperplanes gives faces. My interpretation here is that it is a combinatorial discussion to have "the whole polytope" and "the empty face" included in the poset of faces, as of course adding them makes it a lattice. This act of "adding the trivial faces" forces an eventual consideration of "non-proper/non-trivial" faces when defining anything...

Obviously, things go wrong in the following case:

one removes the non-proper faces and obtains a poset which consists of an anti-chain (can only contain 1 or 2 elements in our case...)

In this case, "vertices" and "facets" are the same. Now you can even go wild and think about the actual object in space (not-being full-dimensional).

If you have one element only, i.e., you have a 0-dimensional polytope, then, what happens combinatorially is that the two elements are fusioned into one and yes, there isn't a bijection between actual maximal subsets given by supporting hyperplanes and the facet defining inequalities.

I would say that the 0-dimensional polytopes form "the exception that confirms the rule", as we say in French. Because of the fact that vertices and facet are the same, this creates this special situation, otherwise, the bijection should exist.

With this perspective, the next step is that

one removes the non-proper faces and obtains an empty poset, for the empty polyhedron. Does the empty polyhedron have facets? I hope not, right?

[kliem]

comment:17

The case where vertices and facets are the same, is for 1-dimensional polyhedra.

[kliem]

comment:18

One other problem with the definition as maximal subfaces (including the empty face) is that it doesn't make any sense for any polyhedron without inequalities. Surely you don't want that the empty face is a facet of RR^2

The 0-dimensional polytope belongs to that family.

The other thing is that the vertex-facet-digraph relies on the fact that vertices are contained in facets or not. If facets are -1-dimensional and vertices 0-dimensional, this doesn't make any sense anymore.

To summarize this discussion, I think we agree that we should alter facets and maybe other methods, such that facets need to be proper faces of polyhedra. Where proper means neither empty nor full-dimensional. Should I open a seperate ticket for it?

[mkoeppe]

comment:19

I think it's fine to do this here on this ticket.

[kliem]

comment:20

I will.

[kliem]

Changed branch from public/29898 to public/29898-reb

[kliem]

New commits:

569cdce	Merge branch 'public/29898' of git://trac.sagemath.org/sage into public/29898-reb
d437956	fix definition of facets

[kliem]

Changed commit from d7cca49 to d437956

[mkoeppe]

comment:23

Typo "non-trival" -> "nontrivial".

When done, you can set "positive review"

[mkoeppe]

Reviewer: Matthias Koeppe

[sagetrac-git]

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

25cfaa0

typo

[sagetrac-git]

Changed commit from d437956 to 25cfaa0

[kliem]

comment:25

Thank you.

[vbraun]

Changed branch from public/29898-reb to 25cfaa0

[kliem]

Changed commit from 25cfaa0 to none