#29898 closed defect (fixed)
vertex facet graph for trivial polyhedra fails
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  geometry  Keywords:  polyhedra, vertex facet graph 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  25cfaa0 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
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 0dimensional polyhedron (it was misbehaved even before #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.)
Change History (27)
comment:1 Changed 10 months ago by
 Branch set to public/29898
 Commit set to 790dfbcad639920619b3d792f728c6d4070bc40f
 Status changed from new to needs_review
comment:2 Changed 10 months ago by
 Commit changed from 790dfbcad639920619b3d792f728c6d4070bc40f to d7cca4927943438b7091e10d036d08b19279f0a2
Branch pushed to git repo; I updated commit sha1. New commits:
d7cca49  correct fix for 0dimensional polyhedron

comment:3 Changed 10 months ago by
Does a 0dimensional polyhedron really have a facet??
comment:4 Changed 10 months ago by
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 1dimensional 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 0dimensional 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 0vector 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 1dimensional face of a Polyhedron in ZZ^1,)
But of course, I might have be influential to "bug fixes" to make it behave like this.
comment:5 Changed 10 months ago by
Hm... the old version of Ziegler's at https://arxiv.org/pdf/math/9909177.pdf says "The maximal nontrivial faces, of dimension dim(P) − 1, are the facets of P."  which excludes the empty face as a possibility.
comment:6 Changed 10 months ago by
I find the version that allows the empty face pretty disturbing.
comment:7 Changed 10 months ago by
Either definition is trouble:
 If you define facets by correspondence with irreducible inequalites than the empty face of the 0dimensional polytope is not a facet. However it is certainly maximal.
 If you define the facets by maximality than you loose that correspondence.
comment:8 Changed 10 months ago by
Either way, I set up the vertexfacet graph wrong. There shouldn't be an edge, as the vertex is not contained in the facet.
comment:9 Changed 10 months ago by
Well the empty face is maximal in the proper faces but not maximal in the nontrivial faces.
comment:10 Changed 10 months ago by
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 nontrival 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.
comment:11 Changed 10 months ago by
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 vertexfacet correspondence for polarity.
Btw the polarity for 0dimensional polyhedra is broken as well (but only for base ring ZZ
):
sage: P = Polyhedron([[]]) sage: P A 0dimensional polyhedron in ZZ^0 defined as the convex hull of 1 vertex sage: P.polar() The empty polyhedron in ZZ^0
comment:12 followup: ↓ 13 Changed 10 months ago by
sage: P = Polyhedron([[]]) sage: P.n_facets() 0 sage: P.facets() (A 1dimensional face of a Polyhedron in ZZ^0,)
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 10 months ago by
 Status changed from needs_review to needs_info
Replying to ghkliem:
sage: P = Polyhedron([[]]) sage: P.n_facets() 0 sage: P.facets() (A 1dimensional face of a Polyhedron in ZZ^0,)
Yes, this is not good.
comment:14 in reply to: ↑ 13 Changed 10 months ago by
Replying to mkoeppe:
Replying to ghkliem:
sage: P = Polyhedron([[]]) sage: P.n_facets() 0 sage: P.facets() (A 1dimensional 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 d1
faces of d
polyhedra.
But I have no hard feelings either way. It just should be made clear that the 0polytope cannot be made consistent in some ways.
comment:15 followup: ↓ 16 Changed 10 months ago by
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).
comment:16 in reply to: ↑ 15 Changed 10 months ago by
Replying to mkoeppe:
Either way, definitely
n_facets()
must be the same as the cardinality offacets()
.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 "nonproper/nontrivial" faces when defining anything...
Obviously, things go wrong in the following case:
one removes the nonproper faces and obtains a poset which consists of an antichain (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 (notbeing fulldimensional).
If you have one element only, i.e., you have a 0dimensional 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 0dimensional 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 nonproper faces and obtains an empty poset, for the empty polyhedron. Does the empty polyhedron have facets? I hope not, right?
comment:17 Changed 10 months ago by
The case where vertices and facets are the same, is for 1dimensional polyhedra.
comment:18 Changed 10 months ago by
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 0dimensional polytope belongs to that family.
The other thing is that the vertexfacetdigraph relies on the fact that vertices are contained in facets or not. If facets are 1dimensional and vertices 0dimensional, 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 fulldimensional. Should I open a seperate ticket for it?
comment:19 Changed 9 months ago by
I think it's fine to do this here on this ticket.
comment:21 Changed 9 months ago by
 Description modified (diff)
comment:22 Changed 9 months ago by
 Branch changed from public/29898 to public/29898reb
 Commit changed from d7cca4927943438b7091e10d036d08b19279f0a2 to d4379565f70a25c335d9f000450fa8239d1d557c
 Status changed from needs_work to needs_review
comment:23 Changed 9 months ago by
 Reviewers set to Matthias Koeppe
Typo "nontrival" > "nontrivial".
When done, you can set "positive review"
comment:24 Changed 9 months ago by
 Commit changed from d4379565f70a25c335d9f000450fa8239d1d557c to 25cfaa04806fdd91dc1d5aebac5b946d10f19f83
Branch pushed to git repo; I updated commit sha1. New commits:
25cfaa0  typo

comment:26 Changed 9 months ago by
 Branch changed from public/29898reb to 25cfaa04806fdd91dc1d5aebac5b946d10f19f83
 Resolution set to fixed
 Status changed from positive_review to closed
comment:27 Changed 8 months ago by
 Commit 25cfaa04806fdd91dc1d5aebac5b946d10f19f83 deleted
 Description modified (diff)
New commits:
fix trivial vertex facet graphs