#29898 closed defect (fixed)
vertex facet graph for trivial polyhedra fails
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.2 |
Component: | geometry | Keywords: | polyhedra, vertex facet graph |
Cc: | jipilab, gh-LaisRast | 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 0-dimensional 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 2 years ago by
- Branch set to public/29898
- Commit set to 790dfbcad639920619b3d792f728c6d4070bc40f
- Status changed from new to needs_review
comment:2 Changed 2 years ago by
- Commit changed from 790dfbcad639920619b3d792f728c6d4070bc40f to d7cca4927943438b7091e10d036d08b19279f0a2
Branch pushed to git repo; I updated commit sha1. New commits:
d7cca49 | correct fix for 0-dimensional polyhedron
|
comment:3 Changed 2 years ago by
Does a 0-dimensional polyhedron really have a facet??
comment:4 Changed 2 years 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 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.
comment:5 Changed 2 years ago by
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.
comment:6 Changed 2 years ago by
I find the version that allows the empty face pretty disturbing.
comment:7 Changed 2 years ago by
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.
comment:8 Changed 2 years ago by
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.
comment:9 Changed 2 years ago by
Well the empty face is maximal in the proper faces but not maximal in the nontrivial faces.
comment:10 Changed 2 years 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 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.
comment:11 Changed 2 years 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 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
comment:12 follow-up: ↓ 13 Changed 2 years ago by
sage: P = Polyhedron([[]]) sage: P.n_facets() 0 sage: P.facets() (A -1-dimensional face of a Polyhedron in ZZ^0,)
comment:13 in reply to: ↑ 12 ; follow-up: ↓ 14 Changed 2 years ago by
- Status changed from needs_review to needs_info
Replying to gh-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.
comment:14 in reply to: ↑ 13 Changed 2 years ago by
Replying to mkoeppe:
Replying to gh-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.
comment:15 follow-up: ↓ 16 Changed 2 years 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 2 years 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 "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?
comment:17 Changed 2 years ago by
The case where vertices and facets are the same, is for 1-dimensional polyhedra.
comment:18 Changed 2 years 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 RR2
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?
comment:19 Changed 2 years ago by
I think it's fine to do this here on this ticket.
comment:21 Changed 2 years ago by
- Description modified (diff)
comment:22 Changed 2 years ago by
- Branch changed from public/29898 to public/29898-reb
- Commit changed from d7cca4927943438b7091e10d036d08b19279f0a2 to d4379565f70a25c335d9f000450fa8239d1d557c
- Status changed from needs_work to needs_review
comment:23 Changed 2 years ago by
- Reviewers set to Matthias Koeppe
Typo "non-trival" -> "nontrivial".
When done, you can set "positive review"
comment:24 Changed 2 years ago by
- Commit changed from d4379565f70a25c335d9f000450fa8239d1d557c to 25cfaa04806fdd91dc1d5aebac5b946d10f19f83
Branch pushed to git repo; I updated commit sha1. New commits:
25cfaa0 | typo
|
comment:26 Changed 2 years ago by
- Branch changed from public/29898-reb to 25cfaa04806fdd91dc1d5aebac5b946d10f19f83
- Resolution set to fixed
- Status changed from positive_review to closed
comment:27 Changed 2 years ago by
- Commit 25cfaa04806fdd91dc1d5aebac5b946d10f19f83 deleted
- Description modified (diff)
New commits:
fix trivial vertex facet graphs